本文主要是介绍2011 ACM/ICPC 北京赛区 J题 Gem and prince，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题很暴力，各种搜索都能过关键是怎么搜。
很重要的剪枝是开一个数组存所有颜色的个数，然后每次搜的时候相应减掉消除的个数，然后比较剩余的分数与当前最大得分，小的话直接返回。 不加这个就会TLE。
然后搜索也不要很裸的每个位置都搜，应该是一块一块的搜，否则会TLE；
| 16180 | 247 | Accepted | 2378ms | 144kb | G++ | 3747B | 2011-10-26 10:48:38 | maddoctor |
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
int n, m, k;
int mp[10][10];
bool v2[10][10];
int xx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int yy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
int cnt, ans, sum;
bool in(int x, int y)
{if(x <= n && x >= 1 && y <= m && y >= 1)return true;return false;
}
void dfs(int x, int y, int tt[10][10], int p, bool vv[10][10])
{vv[x][y] = 1;cnt++;for(int i = 0; i < 8; i++){if(in(x + xx[i], y + yy[i]) && !vv[x + xx[i]][y + yy[i]] && tt[x + xx[i]][y + yy[i]] == p){dfs(x + xx[i], y + yy[i], tt, p, vv);}}
}
void dfs2(int x, int y, int tt[10][10], int p)
{v2[x][y] = 1;tt[x][y] = 0;for(int i = 0; i < 8; i++){if(in(x + xx[i], y + yy[i]) && !v2[x + xx[i]][y + yy[i]] && tt[x + xx[i]][y + yy[i]] == p){dfs2(x + xx[i], y + yy[i], tt, p);}}
}
void move(int tt[10][10])
{int i, j, a[10], cc;for(i = 1; i <= 8; i++)a[i] = 0;for(i = 1; i <= m; i++){cc = 0;for(j = 1; j <= n; j++)if(tt[j][i] > 0){a[++cc] = tt[j][i];}for(j = 1; j <= n - cc; j++)tt[j][i] = 0;for(j = 1; j <= cc; j++){tt[j + n - cc][i] = a[j];}}for(j = 1; j <= m; j++){cc = 0;for(i = 1; i <= n; i++)if(tt[i][j] > 0) cc++;a[j] = cc;}int tp[10];for(i = 1; i <= n; i++){int tc = 0;for(j = 1; j <= m; j++)if(a[j] == 0){continue;}else{tp[++tc] = tt[i][j];}for(j = 1; j <= tc; j++)tt[i][j] = tp[j];for(j = tc + 1; j <= m; j++)tt[i][j] = 0;}
}
void click(int tt[10][10], int s, int *a, int x, int y)
{int i, j;int ta[7], tmp[10][10];bool vv[10][10];int ts = s;for(i = 1; i <= k; i++){if(a[i] >= 3)ts += a[i] * a[i];}if(ts < ans) return;for(int ii = 1; ii <= n; ii++){for(int jj = 1; jj <= m; jj++){vv[ii][jj] = 0;v2[ii][jj] = 0;tmp[ii][jj] = tt[ii][jj];}}if(x != 0 && y != 0)dfs2(x, y, tmp, tmp[x][y]);move(tmp);for(i = 1; i <= n; i++){for(j = 1; j <= m; j++){if(!vv[i][j] && tmp[i][j] > 0){for(int ii = 1; ii <= k; ii++)ta[ii] = a[ii];cnt = 0;dfs(i, j, tmp, tmp[i][j], vv);if(cnt >= 3){ta[tmp[i][j]] -= cnt;click(tmp, s + cnt * cnt, ta, i, j);}}}}ans = max(ans, s);
}
int main()
{//freopen("d:/data.in","r",stdin);//freopen("d:/data.out","w",stdout);int i, j, a[7];while(scanf("%d%d%d", &n, &m, &k) != EOF){memset(a, 0, sizeof(a));memset(v2, 0, sizeof(v2));for(i = 1; i <= n; i++){for(j = 1; j <= m; j++){scanf("%d", &mp[i][j]);if(mp[i][j] > 0)a[mp[i][j]]++;}}ans = 0;click(mp, 0, a, 0 , 0);printf("%d\n", ans);}return 0;
}这篇关于2011 ACM/ICPC 北京赛区 J题 Gem and prince的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
