首页/技術動態

DP! | 不要怂!

 2023-09-05 阅读 63 评论 0

摘要：　　跟一个博客刷：http://blog.csdn.net/cc_again/article/details/25866971 一、简单基础dp 　　1.递推 　　　　HDU 2084 1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int MAXN = 111; 5 int dp[MAXN][MAXN]; 6 int towel[MAXN

　　跟一个博客刷： http://blog.csdn.net/cc_again/article/details/25866971

 

一、简单基础dp

　　1.递推

　　　　HDU 2084

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 111;
 5 int dp[MAXN][MAXN];
 6 int towel[MAXN][MAXN];
 7 
 8 int main(){
 9     int t;
10     scanf("%d", &t);
11     while(t--){
12         memset(towel, 0, sizeof(towel));
13         int n;
14         scanf("%d", &n);
15         for(int i = 0; i < n; ++i)
16             for(int j = 0; j <= i; ++j)
17                 scanf("%d", &towel[i][j]);
18         for(int i = n-1; i > 0; --i)
19             for(int j = 0; j < i; ++j)
20                 towel[i-1][j] += max(towel[i][j], towel[i][j+1]);
21         printf("%d\n", towel[0][0]);
22 /*　
23 *        memset(dp, 0, sizeof(dp));
24 *        dp[0][0] = towel[0][0];
25 *        for(int i = 0; i < n; ++i){
26 *            for(int j = 0; j <= i; ++j){
27 *                dp[i+1][j] = max(dp[i+1][j], dp[i][j]+towel[i+1][j]);
28 *                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+towel[i+1][j+1]);
29 *            }
30 *        }
31 *        int ans = 0;
32 *        for(int i = 0; i < n; ++i)
33 *            ans = max(ans, dp[n-1][i]);
34 *        printf("%d\n", ans);
35 */
36     }
37     return 0;
38 }

 

　　　　HDU 2018

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 66;
 5 int cow[MAXN];
 6 
 7 int main(){
 8     cow[1] = 1;
 9     for(int i = 2; i < MAXN; ++i)
10         cow[i] = i > 4 ? cow[i-1] + cow[i-3] : cow[i-1] + 1;
11     int n;
12     while(scanf("%d", &n) == 1 && n)
13         printf("%d\n", cow[n]);
14     return 0;
15 }

 

　　　　HDU 2044

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int MAXN = 55;
 6 ll cell[MAXN];
 7 
 8 int main(){
 9     int t;
10     scanf("%d", &t);
11     while(t--){
12         int a, b;
13         scanf("%d %d", &a, &b);
14         cell[a] = 1; cell[a+1] = 1;
15         for(int i = a+2; i <= b; ++i)
16             cell[i] = cell[i-1] + cell[i-2];
17         printf("%I64d\n", cell[b]);
18     }
19     return 0;
20 }

 

　　　　HDU 2041

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int MAXN = 50;
 6 ll step[MAXN] = {0, 0, 1, 2, 3};
 7 
 8 int main(){
 9     for(int i = 4; i < MAXN; ++i) step[i] = step[i-1]+step[i-2];
10     int t;
11     scanf("%d", &t);
12     while(t--){
13         int n;
14         scanf("%d", &n);
15         printf("%d\n", step[n]);
16     }
17     return 0;
18 }

 

 

　　　　HDU 2050..............

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main(){
 5     int t;
 6     scanf("%d", &t);
 7     while(t--){
 8         int n;
 9         scanf("%d", &n);
10         printf("%d\n", 2*n*n-n+1);
11     }
12     return 0;
13 }

 

 

　　　　CF 429B

    

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 1e3+7;
 5 int gym[MAXN][MAXN];
 6 int dp[4][MAXN][MAXN];
 7 
 8 // void print(int x, int n, int m){
 9 //     for(int i = 1; i <= n; ++i){
10 //         for(int j = 1; j <= m; ++j)
11 //             printf("%d ", dp[x][i][j]);
12 //         puts("");
13 //     }
14 //     puts("");
15 // }
16 int main(){
17     //while(true){
18         int n, m;
19         scanf("%d %d", &n, &m);
20         for(int i = 1; i <= n; ++i)
21             for(int j = 1; j <= m; ++j)
22                 scanf("%d", &gym[i][j]);
23         memset(dp, 0, sizeof(dp));
24         for(int i = n; i >= 1; --i)
25             for(int j = m; j >= 1; --j)
26                 dp[0][i][j] = max(dp[0][i][j+1], dp[0][i+1][j]) + gym[i][j];
27         for(int i = 1; i <= n; ++i)
28             for(int j = 1; j <= m; ++j)
29                 dp[1][i][j] = max(dp[1][i][j-1], dp[1][i-1][j]) + gym[i][j];
30         for(int i = n; i >= 1; --i)
31             for(int j = 1; j <= m; ++j)
32                 dp[2][i][j] = max(dp[2][i][j-1], dp[2][i+1][j]) + gym[i][j];
33         for(int i = 1; i <= n; ++i)
34             for(int j = m; j >= 1; --j)
35                 dp[3][i][j] = max(dp[3][i-1][j], dp[3][i][j+1]) + gym[i][j];
36         // for(int i = 0; i < 4; ++i)
37         //     print(i, n, m);
38         int ans = 0;
39         for(int i = 2; i < n; ++i)
40             for(int j = 2; j < m; ++j){
41                 ans = max(ans, dp[0][i+1][j] + dp[1][i-1][j] + dp[2][i][j-1] + dp[3][i][j+1]);
42                 ans = max(ans, dp[0][i][j+1] + dp[1][i][j-1] + dp[2][i+1][j] + dp[3][i-1][j]);
43             }
44         printf("%d\n", ans);
45     //}
46     return 0;
47 }

 

 

　　　　ZOJ 3747

 http://blog.csdn.net/cc_again/article/details/24841249

 http://blog.csdn.net/wust_zjx/article/details/46809951

　　　 ans = ((ans - calc(m-1, k)) % MOD + MOD) % MOD; 能减出负数？

 1 #include <bits/stdc++.h>
 2 //#pragma comment(linker, "/STACK:1024000000,1024000000")
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int MOD = 1e9+7;
 7 const int MAXN = 1e6+7;
 8 ll dp[MAXN][5];
 9 ll n, m, k;
10 
11 ll calc(int u, int v){
12 
13     dp[0][2] = 1;
14     dp[0][0] = dp[0][1] = 0;
15 
16     for(int i = 1; i <= n; ++i){
17         ll sum = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % MOD;
18 
19         dp[i][2] = sum;
20 
21         if(i <= u) dp[i][0] = sum;
22         else if(i == u+1) dp[i][0] = sum - 1;
23         else dp[i][0] = sum - dp[i-u-1][1] - dp[i-u-1][2];
24 
25         if(i <= v) dp[i][1] = sum;
26         else if(i == v+1) dp[i][1] = sum - 1;
27         else dp[i][1] = sum - dp[i-v-1][0] - dp[i-v-1][2];
28     }
29 
30     return (dp[n][0] + dp[n][1] + dp[n][2]) % MOD;
31 }
32 int main(){
33     ios::sync_with_stdio(false);
34     //printf("%d %d\n", MAXN, MOD);
35     while(cin >> n >> m >> k){
36         ll ans = calc(n, k);
37         ans = ((ans - calc(m-1, k)) % MOD + MOD) % MOD;
38         cout << ans << endl;
39     }
40     return 0;
41 }

 

 

　　　　uva 10328

　　　怂了不敢撸高精度直接上python    UVA是python3啊.........

 1 while True:
 2     try:
 3         a = [int(i) for i in input().split()]
 4     except:
 5         break
 6 
 7     n = a[0]
 8     k = a[1]
 9 
10     k -= 1;
11     dp = [([0]*2) for i in range(111)]
12 
13     dp[0][0] = 1
14     for i in range(1, n+2):
15         sum = dp[i-1][0] + dp[i-1][1]
16         dp[i][1] = sum
17         #print sum
18         if i < k+1: dp[i][0] = sum
19         if i == k+1: dp[i][0] = sum - 1
20         if i > k+1: dp[i][0] = sum - dp[i-k-1][1]
21         # print i
22         # print dp
23 
24     ans = 1<<n
25     ans -= dp[n+1][1]
26     print(ans)

 

 

　　　　HDU 4747

　　看不懂

　　http://www.cnblogs.com/xin-hua/p/3325154.html

　　http://blog.csdn.net/cc_again/article/details/11856847

 

　　　　HDU 4489

　　　　HDU 4055

 　　2.背包

　　

转载于:https://www.cnblogs.com/book-book/p/5388556.html

版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接：https://hbdhgg.com/4/1177.html

上一篇：一起Polyfill系列：让Date识别ISO 8601日期时间格式
下一篇：UVa 1600 Patrol Robot (习题 6-5)

发表评论:

最新文章
阅读排行
猜你喜欢
热门标签

本站为非赢利网站，部分文章来源或改编自互联网及其他公众平台，主要目的在于分享信息，版权归原作者所有，内容仅供读者参考，如有侵权请联系我们删除！

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息