Baker Vai LightOJ

题意：类似传纸条

方法：

把他要求的操作（一个人来回），转化为两个人同时走，除了开始和结束位置只能走不同路，得到的分数和的最大值即可。

一开始想到要定义的状态，是两个人的x（行）和y（列）坐标。这样时间和空间都为$O(n^4)$，都超出了，因此需要优化。注意到每个人从起点到终点的总步数一定是相同的，而且可以根据每个人走的步数和x坐标，推出这个人的y坐标。那么可以只记录步数和两个人的x坐标作为状态。这样就可以把时间/空间优化到$O(n^3)$。（空间还可以通过滚动数组再优化，但是不优化已经够用）

错误次数：2

原因：

1. 27行错误地写作ans[0][1][1]=1

2. ans第一维错误地与二、三维开了同样的大小（110），实际需要2倍的二、三维

3. 用了C++11的min({..,..})导致CE

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int T,TT,m,n,maxans;

 int ans[][][];

 int a[][];

 int max(int a,int b,int c,int d)

 {

     int ans=a;

     if(b>ans)    ans=b;

     if(c>ans)    ans=c;

     if(d>ans)    ans=d;

     return ans;

 }

 int main()

 {

     int i,j,j1,j2;

     scanf("%d",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%d%d",&m,&n);

         for(i=;i<=m;i++)

             for(j=;j<=n;j++)

                 scanf("%d",&a[i][j]);

         memset(ans,,sizeof(ans));

         ans[][][]=a[][];//起点要特殊处理，两个人在同一位置

         maxans=;

         for(i=;i<=m+n-;i++)

             for(j1=max(,i-n+);j1<=min(i+,m);j1++)//max和min是依据推导出的数据范围

                 for(j2=max(,i-n+);j2<=min(i+,m);j2++)

                     if(j1!=j2)//保证两个人不在同一行，也就是不在同一位置

                         ans[i][j1][j2]=max(ans[i-][j1][j2],ans[i-][j1-][j2],ans[i-][j1][j2-],ans[i-][j1-][j2-])+a[j1][i-j1+]+a[j2][i-j2+];

         i=m+n-;//对于终点也要特殊处理，由于终点两个人可以到同一位置

         for(j1=max(,i-n+);j1<=min(i+,m);j1++)

             for(j2=max(,i-n+);j2<=min(i+,m);j2++)

                 ans[i][j1][j2]=max(ans[i-][j1][j2],ans[i-][j1-][j2],ans[i-][j1][j2-],ans[i-][j1-][j2-])+a[j1][i-j1+]+a[j2][i-j2+];

         for(j1=;j1<=m;j1++)

             for(j2=;j2<=m;j2++)

                 maxans=max(maxans,ans[m+n-][j1][j2]);

         printf("Case %d: %d\n",TT,maxans-a[m][n]);

     }

     return ;

 }

巴特西

Baker Vai LightOJ - 1071

最新文章

热门文章