[POJ 2964 Tourist]双重动态规划

【题目大意】

NOIP的传纸条。不过点权只能为1.

【算法分析】

f[k][i][j]表示走k-2步第一个人走到第i行，第二个人走到第j行，所能达到的最大分数。

之所以搞k-2是因为对于一个人的坐标(i,j)有i+j=k

【其它】1A

= =又在刷水题了。。。。

【CODE】

#include #include #include const int N=1001111;
int m,n;
char a[111][111];
int f[222][111][111];

void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%s",a[i]+1);
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        switch (a[i][j]){
            case ‘.’:a[i][j]=0; break;
            case ‘*’:a[i][j]=1; break;
            case ‘#’:a[i][j]=2; break;
        }   
    memset(f,200,sizeof(f));
}   

inline void max(int &x,int y){
    if (y>x) x=y;
}   

void work(){
    f[2][1][1]=a[1][1];
    for (int k=3;k<=m+n;k++)
      for (int i=1;i<=m;i++) if (k-i<1 || k-i>n) continue; else
        for (int j=1;j<=m;j++) if (k-j<1 || k-j>n) continue; else{
            if (a[i][k-i]==2 || a[j][k-j]==2) continue;
            int &t=f[k][i][j];
            max(t,f[k-1][i-1][j-1]);
            max(t,f[k-1][i-1][j]);
            max(t,f[k-1][i][j-1]);
            max(t,f[k-1][i][j]);
            t+=a[i][k-i];
            if (i!=j) t+=a[j][k-j];
        }   
    max(f[m+n][m][m],0);
    printf("%dn",f[m+n][m][m]);
}   

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int tc;
    scanf("%d",&tc);
    for (int i=1;i<=tc;i++){
      init();
      work();
    }   
}