首页 > 代码库 > [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.截至发表前,这个解法在
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 #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]传纸条
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。