随笔 - 6  文章 - 1  trackbacks - 0
<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜






(讲义是老师从哪里转来的,不是我们老师写的……)
第一题path是水题,注意100 100要用long long存
 1 #include <stdio.h>
 2 long long f[101][101];
 3 int main()
 4 {
 5     int m, n;
 6     scanf("%d%d"&m, &n);
 7     for (int i = 1; i <= 100; i++)
 8         f[i][1= f[1][i] = 1;
 9     for (int i = 2; i <= m; i++)
10         for (int j = 2; j <= n; j++)
11             f[i][j] = f[i - 1][j] + f[i][j - 1];
12     printf("%lld\n", f[m][n]);
13     return 0;
14 }
第二题的path可以在第一题的基础上改进一下,也是道水题
 1 #include <stdio.h>
 2 #include <string.h>
 3 long long f[101][101];
 4 bool p[101][101];
 5 int main()
 6 {
 7     memset(p, falsesizeof(p));
 8     int m, n, t;
 9     scanf("%d%d%d"&m, &n, &t);
10     for (int i = 1, x, y; i <= t; i++)
11     {
12         scanf("%d%d"&x, &y);
13         p[x][y] = true;
14     }
15     f[1][1= 1;
16     for (int i = 1; i <= m; i++)
17     {
18         for (int j = 1; j <= n; j++)
19         {
20             if (i == 1 && j == 1)
21                 continue;
22             if (p[i][j] == true)
23                 f[i][j] = 0;
24             else
25                 f[i][j] = f[i - 1][j] + f[i][j - 1];
26         }
27     }
28     printf("%lld\n", f[m][n]);
29     return 0;
30 }
第三题maxsum,最长连续子序列和,简单但是基础的dp
 1 #include <stdio.h>
 2 #define MAXSIZE 1001
 3 int f[MAXSIZE], a[MAXSIZE], maxn = -1;
 4 int main()
 5 {
 6     int n;
 7     scanf("%d"&n);
 8     for (int i = 1; i <= n; i++)
 9         cin >> a[i];
10     f[1= a[1];
11     for (int i = 2; i <= n ; i++)
12     {
13         f[i] = max(f[i - 1+ a[i], a[i]);
14         maxn = f[i] >= maxn ? f[i] : maxn;
15     }
16     printf("%d\n", maxn);
17     return 0;
18 }
第四题最长不降子序列和,也是简单但是基础的dp题。
 1 #include <stdio.h>
 2 #define MAXSIZE 1001
 3 int a[MAXSIZE], f[MAXSIZE];
 4 int main()
 5 {
 6     int n, max = -1;
 7     scanf("%d"&n);
 8     for (int i = 1; i <= n; f[i] = 1, i++)
 9         scanf("%d", a[i]);
10     for (int i = 2; i <= n; i++)
11         for (int j = 1; j <= i - 1; j++)
12             if (a[i] >= a[j] && f[i] < f[j] + 1)
13                 f[i] = f[j] + 1;
14     for (int i = 1; i <= n; i++)
15         if (f[i] > max)
16             max = f[i];
17     printf("%d\n", f[n]);
18     return 0;
19 }
合唱队形,经典的dp题,双向的最长不降子序列。
 1 #include <stdio.h>
 2 #define MAXSIZE 1001
 3 int f1[MAXSIZE], f2[MAXSIZE], a[MAXSIZE];
 4 int main()
 5 {
 6     int n;
 7     scanf("%d"&n);
 8     for (int i = 1; i <= n; f1[i] = 1, f2[i] = 1, i++)
 9         scanf("%d"&a[i]);
10     for (int i = 2; i <= n; i++)
11         for (int j = 1; j <= i - 1; j++)
12             if (a[i] > a[j] && f2[i] < f2[j] + 1)
13                 f1[i] = f1[j] + 1;
14     for (int i = n - 1; i >= 1; i--)
15         for (int j = n; j >= i + 1; j--)
16             if (a[i] > a[j] && f2[i] < f2[j] + 1)
17                 f2[i] = f2[j] + 1;
18     int max = f1[1+ f2[1- 1;
19     for (int i = 1; i <= n; i++)
20         if (f1[i] + f2[i] - 1 > max)
21             max = f1[i] + f2[i] - 1;
22     printf("%d\n", max);
23     return 0;
24 }
最大的正方形,很基础的dp,但是容易写错,需要仔细的推一下转移方程:f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1
初始化很重要,曾经有一次我错了是因为没写初始化
 1 #include <stdio.h>
 2 #define MAXSIZE 1001
 3 int f[MAXSIZE][MAXSIZE];
 4 int min(int a, int b)
 5 {
 6     if (a > b) return b;
 7     return a;
 8 }
 9 int main()
10 {
11     int m, n, t;
12     scanf("%d%d%d"&m, &n, &t);
13     for (int i = 1; i <= m; i++)
14         for (int j = 1; j <= n; j++)
15             f[i][j] = 1;
16     for (int i = 1, x, y; i <= t; i++)
17     {
18         scanf("%d%d"&x, &y);
19         f[x][y] = 0;
20     }
21     for (int i = 1; i <= m; i++)
22         for (int j = 1; j <= n; j++)
23             if (f[i][j] == 0)
24                 continue;
25             else
26                 f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
27     int max = -1;
28     for (int i = 1; i <= m; i++)
29         for (int j = 1; j <= n; j++)
30             if (f[i][j] > max)
31                 max = f[i][j];
32     printf("%d\n", max);
33     return 0;
34 }
35 
资源分配,是个变形的背包问题,在背包九讲中提到过,难度一般。
 1 #include <stdio.h>
 2 #include <string.h>
 3 int f[11][101], profit[11][101];
 4 int main()
 5 {
 6     int m, n;
 7     memset(f, 0sizeof(f));
 8     scanf("%d%d"&m, &n);
 9     for (int i = 1; i <= n; i++)
10         for (int j = 0; j <= m; j++)
11             scanf("%d"&profit[i][j]);
12     for (int i = 1; i <= n; i++)
13         for (int j = 1; j <= m; j++)
14             for (int k = 0; k <= j; k++)
15                 if (f[i][j] < f[i - 1][j - k] + profit[i][k])
16                     f[i][j] = f[i - 1][j - k] + profit[i][k];
17     printf("%d\n", f[n][m]);
18     return 0;
19 }
20 
posted on 2012-10-04 12:12 某科学的魂魄妖梦 阅读(208) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理