谁有NOIP2008提高组的传纸条的解题报告啊?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/28 18:11:54
谁有NOIP2008提高组的传纸条的解题报告啊?
谁有NOIP2008提高组的传纸条的解题报告啊?
谁有NOIP2008提高组的传纸条的解题报告啊?
这题我以前就看过,一直不会做,后来看到别人说双线程动态规划,我以为是多么多么的神奇的一个东西,把它看的和Linux源码一样神奇了,现在学了之后也就是简单的DP,我用的四维DP,别人都说是三维,我先用四维做,以后再考虑三维（也许不会再考虑这一题了咯.）
我的方程如下:f[a][b][c][d] = max(f[a - 1][b][c - 1][d],f[a][b - 1][c - 1][d],f[a - 1][b][c][d - 1],f[a][b - 1][c][d - 1]) + map[a][b] + map[c][d].
a,b代表第一个线程（说线程夸张了一点）,c,d代表第二个线程的坐标,map就是对应坐标的值.
代码如下：
#include
#define max(a,b) ((a)>(b)?(a):(b))
int f[51][51][51][51];
int map[51][51];
int m,n;
int s[4];
volatile void test(int a,int b,int c,int d,int *t)
{
if(a < 0 || b < 0 || c < 0 || d < 0){
return;
}
*t = max(*t,f[a][b][c][d]);
}
void dp(void)
{
int a = s[0],b = s[1],c = s[2],d = s[3];
int t = 0;
test(a - 1,b,c - 1,d,&t);
test(a - 1,b,c,d - 1,&t);
test(a,b - 1,c,d - 1,&t);
test(a,b - 1,c - 1,d,&t);
f[a][b][c][d] = t + map[a][b] + map[c][d];
}
void srch(int now)
{
int i,k;
if(now == 4){
if(s[0] != s[2] || s[1] != s[3]){
dp();
}
return;
}
if(now & 1){
k = n;
}else{
k = m;
}
for(i = 1; i