【dp入门题】【跟着14练dp吧...囧】

A HDU_2048 数塔

dp入门题——数塔问题；求路径的最大和；

状态方程：

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
dp[n][j] = a[n][j];

其中dp[i][j]: 深度为i的第j个结点的最大和;

 1 /*
 2 Problem: HDU-2048
 3 Tips: Easy DP
 4 dp[i][j]: 深度为i的第j个结点的最大和；
 5 dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
 6 dp[n][j] = a[n][j];
 7 */
 8 #include<iostream>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<cmath>
13 #include<algorithm>
14 using namespace std;
15 typedef long long LL;
16 const int maxn = 110;
17 int a[maxn][maxn], dp[maxn][maxn];
18 int n;
19 void DP()
20 {
21     memset(dp, 0, sizeof(dp));
22     for(int j = 1; j <= n; j++) dp[n][j] = a[n][j];
23     for(int i = n-1; i >= 1; i--)
24     {
25         for(int j = 1; j <= i; j++)
26         {
27             dp[i][j]=max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
28         }
29     }
30     printf("%d
", dp[1][1]);
31 }
32 int main()
33 {
34     int T; scanf("%d", &T);
35     while(T--)
36     {
37         scanf("%d", &n);
38         for(int i = 1; i <= n; i++)
39             for(int j = 1; j <= i; j++)
40                 scanf("%d", &a[i][j]);
41         DP();
42     }
43 
44     return 0;
45 }

View Code

B HDU_1176 免费馅饼

数塔问题变形

状态方程：

dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])+a[i][j]; (注意要从后往前推)

dp[i][10] = max(dp[i+1][j-1], dp[i+1][j])+a[i][10];

dp[i][0] = max(dp[i+1][j], dp[i+1][j+1])+a[i][0];

其中dp[i][j]：第i时刻在位置j的接到的最多馅饼数；

 1 /*
 2 Problem: HDU-2048
 3 Tips: Easy DP
 4 dp[i][j]: 深度为i的第j个结点的最大和;
 5 dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])+a[i][j];
 6 dp[i][10] = max(dp[i+1][j-1], dp[i+1][j])+a[i][10];
 7 dp[i][0] = max(dp[i+1][j], dp[i+1][j+1])+a[i][0];
 8 */
 9 #include<iostream>
10 #include<cstdio>
11 #include<cstdlib>
12 #include<cmath>
13 #include<cstring>
14 #include<string>
15 #include<vector>
16 #include<algorithm>
17 using namespace std;
18 typedef long long LL;
19 const int maxn = 100100;
20 int dp[maxn][15], a[maxn][15];
21 int main()
22 {
23     int n;
24     while(scanf("%d", &n) && n)
25     {
26         memset(a, 0, sizeof(a));
27         int maxt = 0;
28         int t, p;
29         for(int i = 0; i < n; i++)
30         {
31             scanf("%d%d", &p, &t);
32             a[t][p]++;
33             maxt = max(maxt, t);
34         }
35         memset(dp, 0, sizeof(dp));
36         for(int j = 0; j <= 10; j++) dp[maxt][j] = a[maxt][j];
37         for(int i = maxt-1; i >= 0; i--)
38         {
39             for(int j = 1; j <= 9; j++)
40             {
41                 dp[i][j] = max(dp[i+1][j], max(dp[i+1][j+1], dp[i+1][j-1]))+a[i][j];
42             }
43             dp[i][0] = max(dp[i+1][0], dp[i+1][1])+a[i][0];
44             dp[i][10] = max(dp[i+1][10], dp[i+1][9])+a[i][10];
45         }
46 
47         printf("%d
", dp[0][5]);
48     }
49     return 0;
50 }

View Code

C HDU_1087 Super Jumping! Jumping! Jumping!

状态方程：

dp[j] = v[i]<v[j] ? dp[i]+v[j] : dp[j];
dp[0] = 0;
其中dp[j]: 到第j步时，棋子的最大和

感觉自己推的方程毫无技术含量

 1 /*
 2 Problem: HDU-2048
 3 Tips: Easy DP
 4 dp[j]: 到第j步时，棋子的最大和
 5 dp[j] = v[i]<v[j] ? dp[i]+v[j] : dp[j];
 6 dp[0] = 0;
 7 */
 8 #include<iostream>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cmath>
12 #include<cstring>
13 #include<string>
14 #include<vector>
15 #include<algorithm>
16 using namespace std;
17 typedef long long LL;
18 const int maxn = 1010;
19 int dp[maxn], v[maxn];
20 int main()
21 {
22     int n;
23     while(~scanf("%d", &n) && n)
24     {
25         memset(dp, 0, sizeof(dp));
26         int _max = 0;
27         for(int i = 1; i <= n; i++) {scanf("%d", &v[i]); dp[i] = v[i]; _max = max(_max, v[i]);}
28         dp[n+1] = v[n+1] = _max+1; dp[0] = v[0] = 0;
29         for(int i = 1; i <= n; i++)
30         {
31             for(int j = i+1; j <= n+1; j++)
32             {
33                 if(v[j] > v[i])
34                 {
35                     dp[j] = max(dp[j], dp[i]+v[j]);
36                 }
37             }
38         }
39         printf("%d
", dp[n+1]-_max-1);
40     }
41     return 0;
42 }

View Code

E HDU_1058 Humble Numbers

求丑数。两种方法，之前一直用优先队列，dp的算法时间更短，这算法谁想出来的...

每个丑数都可以分解为2^a*3^b*5^c*7的乘积，每次找到最小的数分别乘以2，3，5，7然后放入队列中去。两种方法的基本原理都是这样。

dp：

 1 /*
 2 Problem: HDU 1058
 3 Times: 62MS
 4 Tips: Easy DP
 5 */
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<cstring>
10 #include<queue>
11 #include<stack>
12 #include<algorithm>
13 using namespace std;
14 typedef long long LL;
15 const int maxn = 100100;
16 const int pri[] = {2, 3, 5, 7};
17 LL dp[maxn];
18 LL Min(LL a, LL b, LL c, LL d)
19 {
20     return min(a, min(b, min(c, d)));
21 }
22 
23 void init()
24 {
25     int p1, p2, p3, p4;
26     p1 = p2 = p3 = p4 = 1;
27     dp[1] = 1;
28     int a, b, c, d;
29     for(int i = 2; i <= 5842; i++)
30     {
31         a = dp[p1]*2;
32         b = dp[p2]*3;
33         c = dp[p3]*5;
34         d = dp[p4]*7;
35         dp[i] = Min(a, b, c, d);
36         if(dp[i] == a) p1++;
37         if(dp[i] == b) p2++;
38         if(dp[i] == c) p3++;
39         if(dp[i] == d) p4++;
40     }
41 }
42 
43 int main()
44 {
45     init();
46     int n;
47     while(~scanf("%d", &n) && n)
48     {
49         if(n%10 == 1 && n%100 != 11)
50         {
51             printf("The %dst humble number is %I64d.
", n, dp[n]);
52         }
53         else if(n%10 == 2 && n%100 != 12)
54         {
55             printf("The %dnd humble number is %I64d.
", n, dp[n]);
56         }
57         else if(n%10 == 3 && n%100 != 13)
58         {
59             printf("The %drd humble number is %I64d.
", n, dp[n]);
60         }
61         else
62             printf("The %dth humble number is %I64d.
", n, dp[n]);
63     }
64 
65     return 0;
66 }

View Code

优先队列：

 1 /*
 2 Problem: HDU 1058
 3 Times: 109MS
 4 Tips: Easy DP
 5 */
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<cstring>
10 #include<queue>
11 #include<set>
12 #include<stack>
13 #include<algorithm>
14 #define LL long long
15 using namespace std;
16 //typedef long long LL;
17 const int pri[] = {2, 3, 5, 7};
18 LL ans[6000];
19 
20 void init()
21 {
22     priority_queue<LL, vector<LL>, greater<LL> > pq;
23     set<LL> s;
24     pq.push(1); s.insert(1);
25     for(int i = 1; ; i++)
26     {
27         LL x = pq.top(); pq.pop();
28         ans[i] = x;
29         if(i == 5842)   return ;
30         for(int j = 0; j < 4; j++)
31         {
32             LL t = pri[j]*x;
33             if(!s.count(t))
34             {
35                 s.insert(t);
36                 pq.push(t);
37             }
38         }
39     }
40 }
41 
42 int main()
43 {
44     init();
45     int n;
46     while(~scanf("%d", &n) && n)
47     {
48         if(n%10 == 1 && n%100 != 11)
49         {
50             printf("The %dst humble number is %I64d.
", n, ans[n]);
51         }
52         else if(n%10 == 2 && n%100 != 12)
53         {
54             printf("The %dnd humble number is %I64d.
", n, ans[n]);
55         }
56         else if(n%10 == 3 && n%100 != 13)
57         {
58             printf("The %drd humble number is %I64d.
", n, ans[n]);
59         }
60         else
61             printf("The %dth humble number is %I64d.
", n, ans[n]);
62 
63     }
64     return 0;
65 }

View Code

G HDU_1159 Common Subsequence

LIC入门题+滚动数组

状态方程：

dp[i][j] = (s[i]==s2[j]) ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);

其中dp[i][j] :s1串到i处，s2串到j处时最长上升子串的长度；

由状态方程可以看出，只需要知道i-1时的状态就可以推出i时的状态，因此可以只用一个2*maxn的数组存储状态值，那么看方程也可以根据j-1的状态推出j时的状态啊为什么不用2*2的？虽然方程表面上看来是这样，但是别忘了j是随着i的递增而循环的，每次i改变，状态量都会更新；

 1 /*
 2 Problem: HDU 1159
 3 Tips: LCS
 4 */
 5 
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<cstring>
10 #include<queue>
11 #include<set>
12 #include<stack>
13 #include<algorithm>
14 #define LL long long
15 using namespace std;
16 const int INF = 0x3f3f3f3f;
17 const int maxn = 10100;
18 char s1[maxn], s2[maxn];
19 int dp[5][maxn];
20 void LCS()
21 {
22     int l1 = strlen(s1+1), l2 = strlen(s2+1);
23     memset(dp, 0, sizeof(dp));
24     for(int i = 1; i <= l1; i++)
25     {
26         for(int j = 1; j <= l2; j++)
27         {
28             if(s1[i] == s2[j])
29                 dp[i%2][j] = dp[(i-1)%2][(j-1)]+1;
30             else
31                 dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][(j-1)]);
32         }
33     }
34     printf("%d
", dp[l1%2][l2]);
35 }
36 
37 int main()
38 {
39     while(~scanf("%s%s", s1+1, s2+1))
40     {
41         LCS();
42     }
43     return 0;
44 }

View Code

H HDU_1003 Max Sum

最大连续子串和入门题；blog有原题题解，不再赘述。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<set>
 7 #include<stack>
 8 #include<algorithm>
 9 #define LL long long
10 using namespace std;
11 const int INF = 0x3f3f3f3f;
12 const int maxn = 100100;
13 int n;
14 int a[maxn];
15 int dp[maxn];
16 
17 void DP()
18 {
19     memset(dp, 0, sizeof(dp));
20     int _max = -INF;
21     int s, e; s = e = 0;
22     for(int i = 1; i <= n; i++)
23     {
24         dp[i] = dp[i-1]>0 ? dp[i-1]+a[i] : a[i];
25         if(dp[i] > _max)
26         {
27             _max = dp[i]; e = i;
28         }
29     }
30     printf("%d ", _max);
31     s = e;
32     for(int i = e; i >= 1; i--)
33     {
34             if(dp[i]<0) break;
35             s = i;
36     }
37     printf("%d %d
", s, e);
38 }
39 
40 int main()
41 {
42     int T; scanf("%d", &T);
43     for(int kase = 0; kase < T; kase++)
44     {
45         if(kase) printf("
");
46         printf("Case %d:
", kase+1);
47         scanf("%d", &n);
48         for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
49         DP();
50     }
51     return 0;
52 }

View Code

I HDU_4540 威威猫系列故事——打地鼠

状态方程：

dp[i][j] = min(dp[i-1][pos_last]+abs(pos_last-pos_now));

dp[0][j] = dp[1][j] = 0;

其中dp[i][j]: 第i时刻打位于j位置的地鼠消耗能量的最小值。

 1 /**/
 2 
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 #include<stack>
11 #include<algorithm>
12 #define LL long long
13 using namespace std;
14 const int INF = 0x3f3f3f3f;
15 const int maxn = 25;
16 const int maxp = 510;
17 int n, k;
18 int a[maxn][maxn];
19 int dp[maxn][maxp];
20 void DP()
21 {
22     memset(dp, INF, sizeof(dp));
23     for(int p = 0; p < maxp; p++) dp[1][p] = 0;
24     for(int t = 2; t <= n; t++)
25         for(int j = 0; j < k; j++)
26     {
27         int pos_now = a[t][j];
28         int _min = INF;
29         for(int p = 0; p < k; p++)
30         {
31             int pos_last = a[t-1][p];
32             _min = min(_min, dp[t-1][pos_last]+abs(pos_last-pos_now));
33         }
34         dp[t][pos_now] = _min;
35     }
36     int _min = dp[n][0];
37     for(int p = 0; p < k; p++)
38         _min = min(_min, dp[n][a[n][p]]);
39     printf("%d
", _min);
40 }
41 
42 int main()
43 {
44     while(~scanf("%d%d", &n, &k))
45     {
46         for(int t = 1; t <= n; t++)
47             for(int p = 0; p < k; p++)
48                 scanf("%d", &a[t][p]);
49         DP();
50     }
51     return 0;
52 }

View Code