首页 > 代码库 > [NOIP2008]传纸条

[NOIP2008]传纸条

     暂时不会写费用流,先用双线动规写一遍,下午再来写费用流解法= =

解法1:双线动规

     首先我们不难看出,由于纸条回来时不能与去时的路径重叠,“一来一回”和“从左上角分两条路走向右下角”这两个模型是等价的。于是我们可以把两条路到达的端点同时作为状态保存下来(dp[x1][y1][x2][y2])。又因为矩阵图的特殊性,左上角到右下角的所有路径长度均为两点的曼哈顿距离,我们可以让两点”同时“移动,即任何时刻两点走过的路程相同。这样,我们可以记当前状态为dp[i, j, k],其中 i 表示当前两点走到的横纵坐标之和,j表示第一条路径走到的横坐标,k表示第二条路径走到的横坐标。考虑到两条路径在途中不能重叠,我们约定j > k。其中每个位置最多都可以由两个点达到,那么每种状态最多要考虑2*2=4种前驱。这里要考虑一种特殊情况:当k == j-1时,两点都可以由(k, i-k-1)这一点走到,然而题目中规定路径中不能有重叠,那么这时我们应当排除”两点从同一点转移得到“的情况╮(╯▽╰)╭

    这样,这道题就完美解决了→_→

    p.s.截至发表前,这个解法在COGS上排到了速度rank1→_→

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cctype>
 5 #include <cmath>
 6 #define maxn (52)
 7 using namespace std;
 8 #ifdef DEBUG
 9 FILE *in = fopen("test","r");
10 #define out stdout
11 #else
12 FILE *in = fopen("message.in","r");
13 FILE *out = fopen("message.out","w");
14 #endif
15 
16 inline void getint(int &k){
17     char c = fgetc(in);
18     while(!isdigit(c))c = fgetc(in);
19     k = c - 0;
20     while(isdigit(c = fgetc(in)))
21         k = k * 10 + (c - 0);
22 }
23 int m, n;
24 int Mat[maxn][maxn];//坐标从1开始
25 int dp[maxn<<1][maxn][maxn] = {0};
26 int main(){
27     int i, j, k, Max, t;
28     getint(m),getint(n);
29     for(i = 1;i <= m;++i)
30         for(j = 1;j <= n;++j)getint(Mat[i][j]);
31     dp[3][2][1] = Mat[2][1] + Mat[1][2];
32     for(i = 4;i < m+n;++i)
33         for(j = 2;j <= m;++j){
34             if(j == i)break;
35             for(k = max(1,i-n);k < j;++k){
36                 Max = dp[i-1][j][k];
37                 if((t=dp[i-1][j][k-1]) > Max)Max = t;
38                 if((t=dp[i-1][j-1][k-1]) > Max)Max = t;
39                 if(k!=j-1 && (t=dp[i-1][j-1][k])>Max)Max = t;
40                 dp[i][j][k] = Max + Mat[j][i-j] + Mat[k][i-k];
41             }
42         }
43     i = m + n - 1;
44     fprintf(out,"%d\n",dp[i][m][m-1]);
45     return 0;
46 }
双线动规

 解法2:最大费用最大流

    还没学网络流,下午再写= =

 

 

 

 

 

 

 

 

 

 

 

 

[NOIP2008]传纸条