[HOJ 192][Codeforces #131]撿肥皂

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這題要求不繞路，所以可以設計一個DP，DP[i0][j0][i1][j1]代表A走到(i0,j0)，B走到(i1,j1)時，兩人目前最多撿到幾塊肥皂
可是題目要求重複走過的地方只能算一次，而且以上DP對於N=300時會TLE+MLE，怎麼辦呢？
思路是「同步化」，可以發現，不管是誰，每走一步就會讓x+y這個數字+1，而且兩人走得步數最後是一樣的，因此可以一步一步來DP，DP[sum][i0][j0]代表x+y為sum時，A走到y=i0，B走到y=i1，兩人撿得肥皂總和最多多少
這樣，走到重複的格子也好處理了
有兩項優化可以套用，不過沒有也沒關係
1. 滾動陣列
2. 限制A的y一定要<=B的y
時間複雜度O(N^3)

code:

#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=2147483647;
void getmax(int &a,const int b){if(b>a)a=b;}
int N,GRID[300][300],DP[2][300][300];
int GetSoap(const int i0,const int j0,const int i1,const int j1)
{
    if(i0==i1&&j0==j1)return GRID[i0][j0];
    return GRID[i0][j0]+GRID[i1][j1];
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)scanf("%d",&GRID[i][j]);
        for(int d=0;d<2;d++)for(int i=0;i<N;i++)for(int j=i;j<N;j++)DP[d][i][j]=-INF;
        DP[0][0][0]=GRID[0][0];
        int d=0;
        for(int sum=0;sum<(N-1)*2;sum++,d^=1)
        {
            for(int i0=0,j0;i0<=sum&&i0<N;i0++)if((j0=sum-i0)<N)
            {
                for(int i1=i0,j1;i1<=sum&&i1<N;i1++)if((j1=sum-i1)<N)
                {
                    const int dp=DP[d][i0][i1];if(dp==-INF)continue;
                    if(i0+1<N)
                    {
                        if(i1+1<N)getmax(DP[d^1][i0+1][i1+1],dp+GetSoap(i0+1,j0,i1+1,j1));
                        if(j1+1<N&&i0+1<=i1)getmax(DP[d^1][i0+1][i1],dp+GetSoap(i0+1,j0,i1,j1+1));
                    }
                    if(j0+1<N)
                    {
                        if(i1+1<N)getmax(DP[d^1][i0][i1+1],dp+GetSoap(i0,j0+1,i1+1,j1));
                        if(j1+1<N)getmax(DP[d^1][i0][i1],dp+GetSoap(i0,j0+1,i1,j1+1));
                    }
                    DP[d][i0][i1]=-INF;
                }
            }
        }
        printf("%d\n",DP[d][N-1][N-1]);
        break;
    }
    return 0;
}