题面：
Civilization
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 372 Accepted Submission(s): 90
Problem Description
这是一个回合制游戏，每一回合开始前会进行上一回合的结算。
有一张 n∗n 的棋盘，我们出生在一个初始位置 (x,y)，现在我们要选择一个位置建设城市。
你的人物每回合可以移动到距离你曼哈顿距离不超过 2 的位置，移动完成后可以选择是否建立城市。
建立城市后，你的人物消失，成为一个人口为 1 的城市，这个人口要下回合才可以工作。如果不移动，直接在 (x,y) 建城，第 1 回合就可以开始工作。
对于城市的每个居民，你可以安排他到距离城市曼哈顿距离小于等于 3 的位置进行工作，此居民可以瞬间到达该位置，每个位置最多安排一个居民，失业的人口不会生产任何食物。
注意，城市位置上必须有一个居民在工作。
结算按照如下顺序：
- 如果位置 (i,j) 上有一个工作居民，则获得 a[i][j] 的食物。
- 如果当前城市人口为 i，且食物达到 8∗i2 时，你获得一个新的居民，下一回合可以进行操作。
当结算后城市总人口达到 9 游戏结束。
初始食物数量为 0，人口上涨不会导致之前积累的食物消失。输出最少几个回合能让游戏结束。
Input
第一行一个正整数 test(1≤test≤10) 表示数据组数。
对于每组数据，第一行三个正整数 n(2≤n≤500),x(1≤x≤n),y(1≤y≤n)，分别表示棋盘大小和起始位置。
接下来 n 行，每行 n 个整数，第 i 行第 j 列的整数表示 a[i]j。
Output
对于每组数据，一行一个整数表示答案。
Sample Input
1
10 9 8
1 2 2 1 2 3 1 1 2 1
2 1 3 3 3 2 3 2 3 1
1 1 3 1 1 3 2 2 1 2
3 1 3 1 3 3 1 3 1 3
3 2 3 1 3 1 2 2 2 1
2 3 2 3 2 2 3 1 2 3
3 1 3 3 2 2 3 2 3 3
1 3 3 2 3 2 2 2 1 1
3 3 1 2 3 2 1 2 1 2
1 1 3 1 3 1 1 1 3 3
Sample Output
39
题解：
枚举每个点，然后考虑在这一点建立城市需要的回合。
如果有可以离开城市这一点的人口，一定是去可获得食物最多的地方，来使得回合数最少。
求在某一点建立城市所需要的回合时，对于某一个区间 第 i 个人到 第 i+1 之间的每回合获得的食物是固定的，那么我们期望复杂度O（9）就可以算出某一点需要的回合数。
那么总的复杂度就是 O(T∗n2∗9)。（其实还有算周围曼哈顿距离小于等于3的点的权值的时间复杂度大约 O(24)或者O(81)，那么应该是 O(T∗n2∗81)）
因为求某一点的回合数的时候，比赛的时候是暴力求的，大约需要600次左右，时间复杂度大概是 O(T∗n3) ，就T了。
我们设 ans[x][i][j][k]为在权值为x的点建立城市，周围有 i 个1， j 个2， k 个3的时候需要多少回合结束游戏。
预处理复杂度是 O(3∗25∗25∗25∗500∗log25),虽然也很接近 O(n3)了，但是还是过了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=550;
const int maxm=100100;
const int up=24;
int a[maxn][maxn];
int n,sx,sy,minn;
int xx[]={-3,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,0,1,1,1,1,1,2,2,2,3};
int yy[]={0,-1,0,1,-2,-1,0,1,2,-3,-2,-1,1,2,3,-2,-1,0,1,2,-1,0,1,0};
int ans[4][25][25][25];
multiset<int>se;
int dis(int x,int y)
{
int len=abs(x-sx)+abs(y-sy);
return len/2+len%2;
}
bool check(int x,int y)
{
if(x<1||x>n||y<1||y>n) return false;
return true;
}
int get(int x,int y)
{
int p[4]={0,0,0,0};
for(int i=0;i<up;i++)
{
int nx=x+xx[i];
int ny=y+yy[i];
if(check(nx,ny));
p[a[nx][ny]]++;
}
return ans[a[x][y]][p[1]][p[2]][p[3]];
}
void init(void)
{
for(int i=0;i<=24;i++)
{
for(int j=0;j<=24;j++)
{
for(int k=0;k<=24;k++)
{
if(i+j+k>24) break;
se.clear();
for(int m=1;m<=i;m++)
se.insert(1);
for(int m=1;m<=j;m++)
se.insert(2);
for(int m=1;m<=k;m++)
se.insert(3);
for(int pk=1;pk<=3;pk++)
{
multiset<int>ss=se;
int one=pk,num=1,now=0,sum=0,aans=1;
while(num<9)
{
now++;
sum+=one;
if(sum>=8*num*num) num++;
if(num>aans)
{
if(ss.size()!=0)
{
aans++;
one+=*(--ss.end());
ss.erase(--ss.end());
}
}
}
ans[pk][i][j][k]=now;
}
}
}
}
}
int main(void)
{
init();
int tt;
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d%d",&n,&sx,&sy);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
minn=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
minn=min(minn,dis(i,j)+get(i,j));
printf("%d\n",minn);
}
return 0;
}
京公网安备 11010502036488号