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

[NOIP2008]传纸条

2024-07-25 18:01:05   217人阅读

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

解法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]传纸条


联系
我们