首先 来回传纸条 可以看作从左上向右下传2次纸条（同时）

function dis(a,b:longint):longint;

begin

dis:=a-1+b-1;

end;

4维DP时 加一个判断：

if dis(x1,y1)=dis(x2,y2) then DP

可以剪掉不少的数据

因为同时传2张纸条 取最大值

若用（X1，Y1）（X2，Y2）两点坐标来表示当前状态的话

则

这两点到出发点距离一定相等

即dis(x1,y1)〈〉dis(x2,y2)的状态不存在

。。

比较得 当N很大时 优化很有效

见下

优化前

查看状态 Show Status

题目:[NOIP2008]传纸条

状态: Accepted

测评机： Xeost[5]

得分： 100分 [我要评价一下题目~]

提交日期： 2012-6-29 16:05:00

有效耗时： 2703毫秒

测试结果1: 通过本测试点|有效耗时188ms

测试结果2: 通过本测试点|有效耗时156ms

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时172ms

测试结果5: 通过本测试点|有效耗时172ms

测试结果6: 通过本测试点|有效耗时203ms

测试结果7: 通过本测试点|有效耗时453ms

测试结果8: 通过本测试点|有效耗时375ms

测试结果9: 通过本测试点|有效耗时422ms

测试结果10: 通过本测试点|有效耗时390ms

优化后

查看状态 Show Status

题目:[NOIP2008]传纸条

状态: Accepted

测评机： Xeost[5]

得分： 100分 [我要评价一下题目~]

提交日期： 2012-6-29 15:55:00

有效耗时： 2172毫秒

测试结果1: 通过本测试点|有效耗时203ms

测试结果2: 通过本测试点|有效耗时156ms

测试结果3: 通过本测试点|有效耗时156ms

测试结果4: 通过本测试点|有效耗时172ms

测试结果5: 通过本测试点|有效耗时172ms

测试结果6: 通过本测试点|有效耗时172ms

测试结果7: 通过本测试点|有效耗时359ms

测试结果8: 通过本测试点|有效耗时266ms

测试结果9: 通过本测试点|有效耗时266ms

测试结果10: 通过本测试点|有效耗时250ms

回复 板凳wsxtyrdd 的帖子

看哥的！

#include<iostream>

using namespace std;

int m,n,i,j,k,s[101][101],dp[101][101][101],ans;

int main()

{

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

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

for (j=1;j<=n;j++) scanf("%d",&s[i][j]);

memset(dp,0,sizeof(dp));

dp[3][1][2]=s[2][1]+s[1][2];

for (k=4;k<m+n;k++)

{

for (i=1;i<k;i++)

if (k-i<=m)

{

for (j=i+1;j<k;j++)

if (k-j<=m)

{

if (i!=1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j-1]);

if (i!=1 && j!=k-1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j]);

if (j-i!=1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j-1]);

if (j!=k-1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]);

dp[k][i][j]+=s[k-i][i]+s[k-j][j];

}

}

}

if (m==1 || n==1) ans=0;

else ans=dp[m+n-1][n-1][n];

printf("%d\n",ans);

//system("pause");

return 0;

}

Accepted

测评机： Xeost[5]

得分： 100分

提交日期： 2013-7-14 14:36:00

有效耗时： 1061毫秒

测试结果1: 通过本测试点|有效耗时234ms

测试结果2: 通过本测试点|有效耗时78ms

测试结果3: 通过本测试点|有效耗时47ms

测试结果4: 通过本测试点|有效耗时188ms

测试结果5: 通过本测试点|有效耗时218ms

测试结果6: 通过本测试点|有效耗时62ms

测试结果7: 通过本测试点|有效耗时47ms

测试结果8: 通过本测试点|有效耗时47ms

测试结果9: 通过本测试点|有效耗时62ms

测试结果10: 通过本测试点|有效耗时78ms

测试点1 Accepted / 34ms / 6564kB

测试点2 Accepted / 26ms / 6564kB

测试点3 Accepted / 35ms / 6564kB

测试点4 Accepted / 46ms / 6564kB

测试点5 Accepted / 32ms / 6564kB

测试点6 Accepted / 39ms / 6564kB

测试点7 Accepted / 34ms / 6564kB

测试点8 Accepted / 51ms / 6564kB

测试点9 Accepted / 30ms / 6564kB

测试点10 Accepted / 34ms / 6564kB

测试点1 Accepted / 0ms / 7260kB

测试点2 Accepted / 0ms / 7260kB

测试点3 Accepted / 0ms / 7260kB

测试点4 Accepted / 0ms / 7260kB

测试点5 Accepted / 0ms / 7260kB

测试点6 Accepted / 0ms / 7260kB

测试点7 Accepted / 8ms / 7260kB

测试点8 Accepted / 10ms / 7260kB

测试点9 Accepted / 9ms / 7260kB

测试点10 Accepted / 9ms / 7260kB