DP专题(不定期更新)

1、UVa 11584 Partitioning by Palindromes(字符串区间dp)

　　题意：给出一个字符串，划分为若干字串，保证每个字串都是回文串，同时划分数目最小。

　　思路：dp[i]表示以第i位结尾时最小的划分数目(初始均为0)

　　　　状态转移方程1：(初始均为0)当[j:i]是回文串（0≤j≤i，0≤i<n）:dp[i]=1(j==0);dp[i]=(dp[i]==0?dp[j-1]+1:min(dp[i],dp[j-1]+1))

　　　　状态转移方程2：(初始：dp[i]=i+1)当[j:i]是回文串（0≤j≤i，0≤i<n）:dp[i]=1(j==0);dp[i]=min(dp[i],dp[j-1]+1))

　　　　状态转移方程3：(初始：dp[i]=i+1(1≤i≤n);其他：dp[i]=0)当[j:i]是回文串（1≤j≤i，1≤i≤n）:dp[i]=min(dp[i],dp[j-1]+1))

 1 #include<iostream>
 2 #include<memory.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<cstdio>
 6 using namespace std;
 7 const int maxn = 1005;
 8 char s[maxn];
 9 int dp[maxn];
10 int n;
11 bool Judge(int st, int ed)
12 {
13     for (; st <= ed; st++, ed--)
14     {
15         if (s[st] != s[ed]) return false;
16     }
17     return true;
18 }
19 int main()
20 {
21     cin >> n;
22     while (n--)
23     {
24         scanf("%s", s);
25         memset(dp, 0, sizeof(dp));
26         int sz = strlen(s);
27         for (int i = 0; i < sz; i++)
28         {
29             for (int j = 0; j <= i; j++)
30             {
31                 if (Judge(j, i))
32                 {
33                     if (j == 0) dp[i] = 1;
34                     else dp[i] = dp[i] == 0 ? dp[j - 1] + 1 : min(dp[i], dp[j - 1] + 1);
35                 }
36             }
37         }
38         cout << dp[sz - 1] << endl;
39     }
40     return 0;
41 }

View Code

2、UVA 10534 Wavio Sequence(dp + LIS)

　　题意：给出一个字符串,求满足这样条件的子序列的最大长度：长度为奇数（假设为2*k+1），同时前k+1个严格递增，后k+1个严格递减。

　　思路：分别从左往右和从右往左分别算出以第i位结尾的最长递增子序列的长度L1、L2，然后得出以第i位为中点的满足条件的子序列的长度：min(L1,L2)*2-1（如果L1、L2包含该位），然后对每一位分别重复上述操作，得出最大长度。

 1 #include<iostream>
 2 #include<vector>
 3 #include<memory.h>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 10005;
 7 int maxl[maxn];
 8 int maxr[maxn];
 9 int p[maxn];
10 void exchange(int x, int pos, vector<int>&v, char c)
11 {
12     vector<int>::iterator it;
13     it = lower_bound(v.begin(), v.end(), x);
14     int p = it - v.begin();
15     v[p] = x;
16     if (c == 'l')maxl[pos] = p;
17     else maxr[pos] = p;
18 }
19 int main()
20 {
21     int n;
22     while (cin >> n)
23     {
24         vector<int>minlen;
25         for (int i = 0; i < n; i++) cin >> p[i];
26         minlen.push_back(p[0]);
27         maxl[0] = 0;
28         for (int i = 1; i < n; i++)
29         {
30             if (p[i] > minlen.back())
31             {
32                 maxl[i] = minlen.size();
33                 minlen.push_back(p[i]);
34             }
35             else
36             {
37                 exchange(p[i], i, minlen, 'l');
38             }
39         }
40         minlen.clear();
41         minlen.push_back(p[n - 1]);
42         maxr[n - 1] = 0;
43         for (int i = n - 2; i >= 0; i--)
44         {
45             if (p[i] > minlen.back())
46             {
47                 maxr[i] = minlen.size();
48                 minlen.push_back(p[i]);
49             }
50             else
51             {
52                 exchange(p[i], i, minlen, 'r');
53             }
54         }
55         int len = 0;
56         for (int i = 0; i < n; i++)
57         {
58             int tmp = min(maxl[i], maxr[i]) * 2 + 1;
59             if (tmp > len) len = tmp;
60         }
61         cout << len << endl;
62     }
63     return 0;
64 }

View Code

3、uva 11404 - Palindromic Subsequence(dp)

　　题意：给出一个字符串，求其最长回文子串，并输出该字串。如果有多个，输出字典序最小的那个。

　　思路：如果只求长度：dp[i][j]=dp[i+1][j-1]+2(s[i]==s[j]);dp[i][j]=max(dp[i+1][j],dp[i][j-1])(s[i]!=s[j])

　　　　在此基础上可以用string来保存临时回文子串。

 1 #include<iostream>
 2 #include<string>
 3 #include<memory.h>
 4 using namespace std;
 5 const int maxn = 1005;
 6 struct node
 7 {
 8     int len;
 9     string str;
10 }dp[maxn][maxn];
11 
12 int main()
13 {
14     string s;
15     while (cin >> s)
16     {
17         int len = s.length();
18         memset(dp, 0, sizeof(dp));
19         for (int i = 0; i < len; i++)
20         {
21             dp[i][i].len = 1;
22             dp[i][i].str = s[i];
23         }
24         for (int i = len - 1; i >= 0; i--)
25         {
26             for (int j = i; j < len; j++)
27             {
28 
29                 if (s[i] == s[j])
30                 {
31                     if (i == j)
32                     {
33                         dp[i][j].len = 1;
34                         dp[i][j].str = s[i];
35                     }
36                     else
37                     {
38                         dp[i][j].len = dp[i + 1][j - 1].len + 2;
39                         dp[i][j].str = s[i] + dp[i + 1][j - 1].str + s[j];
40                     }
41                 }
42                 else
43                 {
44                     if (dp[i + 1][j].len > dp[i][j - 1].len)
45                     {
46                         dp[i][j].len = dp[i + 1][j].len;
47                         dp[i][j].str = dp[i + 1][j].str;
48                     }
49                     else if (dp[i + 1][j].len < dp[i][j - 1].len)
50                     {
51                         dp[i][j].len = dp[i][j - 1].len;
52                         dp[i][j].str = dp[i][j - 1].str;
53                     }
54                     else
55                     {
56                         dp[i][j].len = dp[i][j - 1].len;
57                         if (dp[i][j - 1].str < dp[i + 1][j].str) dp[i][j].str = dp[i][j - 1].str;
58                         else dp[i][j].str = dp[i + 1][j].str;
59                     }
60                 }
61             }
62         }
63         cout << dp[0][len - 1].str << endl;
64     }
65     return 0;
66 }

View Code

4、UVA 11795 - Mega Man's Mission(状态压缩dp)

　　题意：洛克人手里有一把武器，能够杀死部分特定敌人（可以杀死的记为1，无法杀死的记为0），同时，他杀死敌人后，能够使用被杀死的敌人的武器，其武器同样也只能杀死特定的敌人。求能杀死所有敌人的方案数。

　　思路：对于n个敌人，共有2^n-1种状态（用一个int即可表示），可以先求出每种状态下能够杀死的敌人atk[i]（即该状态i下杀死的敌人的武器被获得后能够杀死的敌人），之后，对于i这种状态，如果该状态下能够杀死敌人j,如果i^(1<<j)这种状态(不能杀死j)下能够杀死j(atk[i^(1<<j)]&1<<j),则dp[i]+=dp[i^(1<<j)]。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<memory.h>
 4 using namespace std;
 5 typedef long long ll;
 6 char s[20];
 7 const int maxn = (1 << 16) + 10;
 8 int N;
 9 int w[maxn];//存储洛克人[0]和敌人[1:]的武器
10 int atk[maxn];//用来保存每个状态可以杀死的机器人
11 ll dp[maxn];// 2 的 16 次方会爆 int。 // 用来统计每种状态的顺序方案种数
12 int Exchange()
13 {
14     int ans = 0;
15     int sz = strlen(s);
16     for (int i = 0; i < sz; i++)
17     {
18         if (s[i] == '1') ans = ans | (1 << i);//第i+1位如果能被杀掉，则第i+1位为1
19     }
20     return ans;
21 }
22 int main()
23 {
24     int T;
25     cin >> T;
26     int Case = 1;
27     while (T--)
28     {
29         cin >> N;
30         for (int i = 0; i <= N; i++)
31         {
32             scanf("%s", s);
33             w[i] = Exchange();
34             //cout << i << ' ' << w[i] << endl;
35         }
36         int total = (1 << N) - 1;//对于N个敌人，一共最多有2^N-1种状态（每个敌人能够杀死或不能杀死）
37         for (int st = 0; st <= total; st++)
38         {//st即为二进制存储的状态
39             atk[st] = w[0];//初始为洛克人所拿的武器能够杀死的人
40             for (int i = 1; i <= N; i++)//对于每个敌人
41             {
42                 int j = i - 1;//i其在所存二进制里的位置
43                 if (st&(1 << j))
44                 {//如果该状态可以杀死 i，那么该状态也可以杀死i所能干掉的
45                     atk[st] = atk[st] | w[i];
46                 }
47             }
48         }
49         memset(dp, 0, sizeof(dp));
50         dp[0] = 1;//一个都不杀死的方案数为1
51         for (int st = 1; st <= total; st++)
52         {
53             for (int i = 0; i < N; i++)
54             {//对于N个敌人
55                 if (st & 1 << i)
56                 {//如果该状态能够杀死第i+1个敌人(敌人从1开始编号，但是在二进制存储的杀死状态中存储的位置为i),那么 st 由不能杀死 i 的状态转移过来, 即st^(1<<i)（异或）
57                     if (atk[st ^ (1 << i)] & 1 << i)//并且st^(1<<i)这种状态能够杀死该敌人
58                     {
59                         dp[st] += dp[st ^ (1 << i)];
60                     }
61                 }
62             }
63         }
64         printf("Case %d: %lld
", Case++, dp[total]);
65     }
66     return 0;
67 }

View Code

5、UVA 10564 Paths through the Hourglass(dp)

　　题意：有一个漏斗形的图，从某一行只能向左下或右下走，走过的路径上的点数之和要等于S。求路径数，若存在，则输出从第一行最左侧开始，同时所走方向形成的字典序最小的字符串。（由‘L’、‘R’组成）。

　　思路：从下往上dp,dp[i][j][k] 代表从(i, j)点往下走到最后一层和为k的方案数,那么，显然可以得到状态转移：

　　dp[i][j][k] = dp[i + 1][left][k - val] + dp[i + 1][right][k - val], val = (i, j)格上的数字，left是往坐下走的坐标，right往右下走的坐标

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<cstdio>
  4 using namespace std;
  5 typedef long long ll;
  6 int N, S;
  7 ll dp[50][50][510];
  8 int m[50][50];
  9 void Input()
 10 {
 11     for (int i = 1; i <= N; i++)
 12     {
 13         for (int j = 1; j <= N - i+1; j++)
 14         {
 15             scanf("%d", &m[i][j]);
 16         }
 17     }
 18     for (int i = N+1; i <= 2 * N - 1; i++)
 19     {
 20         for (int j = 1; j <= i - N + 1; j++)
 21         {
 22             scanf("%d", &m[i][j]);
 23         }
 24     }
 25 }
 26 void Print()
 27 {
 28     int pos;
 29     for (int i = 1; i <= N; i++)
 30     {
 31         if (dp[1][i][S])
 32         {
 33             cout <<i-1<< ' ';
 34             pos = i;
 35             break;
 36         }
 37     }
 38     int sum = S;
 39     for (int i = 2; i <= N; i++)
 40     {
 41             if (dp[i][pos - 1][sum - m[i - 1][pos]])
 42             {
 43                 cout << 'L';
 44                 sum -= m[i - 1][pos];
 45                 pos--;
 46             }
 47             else
 48             {
 49                 cout << 'R';
 50                 sum -= m[i - 1][pos];
 51             }
 52     }
 53     for (int j = N+1; j <= 2 * N - 1; j++)
 54     {
 55         if (dp[j][pos][sum - m[j - 1][pos]])
 56         {
 57             cout << 'L';
 58             sum -= m[j - 1][pos];
 59         }
 60         else
 61         {
 62             cout << 'R';
 63             sum -= m[j - 1][pos];
 64             pos++;
 65         }
 66     }
 67     cout << endl;
 68 }
 69 
 70 int main()
 71 {
 72     while (cin >> N >> S, N != 0 || S != 0)
 73     {
 74         Input();
 75         memset(dp, 0, sizeof(dp));
 76         for (int i = 1; i <= N; i++) dp[2 * N - 1][i][m[2 * N - 1][i]] = 1;
 77         for (int i = 2 * N - 2; i >= N; i--)
 78         {
 79             for (int j = 1; j <= i - N + 1; j++)
 80             {
 81                 int v = m[i][j];
 82                 for (int tv = v; tv <= S; tv++)
 83                 {
 84                     dp[i][j][tv] = dp[i + 1][j][tv-v] + dp[i + 1][j + 1][tv-v];
 85                 }
 86             }
 87         }
 88         for (int i = N - 1; i >= 1; i--)
 89         {
 90             for (int j = 1; j <= N - i+1; j++)
 91             {
 92                 int v = m[i][j];
 93                 for (int tv = v; tv <= S; tv++)
 94                 {
 95                     dp[i][j][tv] = dp[i + 1][j][tv-v] + dp[i + 1][j - 1][tv-v];
 96                 }
 97             }
 98         }
 99         ll ans = 0;
100         for (int i = 1; i <= N; i++) ans += dp[1][i][S];
101         if (ans == 0) cout << ans << endl << endl;
102         else
103         {
104             printf("%lld
", ans);
105             Print();
106         }
107     }
108     return 0;
109 }

View Code

6、UVA 11552 Fewest Flops

　　题意：给出一个长度能够整除k的字符串，整除后得到的子串中的字符看可以重新组合。求最后得到的新的字符串中满足该条件（字串中每个字符都相同）的子串的最小数目。例如：“abccd”中，这样的数目有4个：“a”,"b","cc","d".

　　思路：DP[i][j]表示前i段，第i段以第j个字符结尾时最小的满足条件的字串数目。

　　　　DP[i][j] = min(DP[i][j],DP[i - 1][l] + cnt - 1)(i-1段以第l个字符结尾时，该字符和第i段第一个字符相同时)

　　　　DP[i][j] = min(DP[i][j],DP[i - 1][l] + cnt)(i-1段以第l个字符结尾时，该字符和第i段第一个字符不同时)

 1 #include<map>
 2 #include<string>
 3 #include<iostream>
 4 #include<memory.h>
 5 #include<algorithm>
 6 using namespace std;
 7 #define maxn 1020
 8 int dp[maxn][maxn];
 9 int main()
10 {
11     int n;
12     cin >> n;
13     while (n--)
14     {
15         int k;
16         cin >> k;
17         string s;
18         cin >> s;
19         int l = s.length();
20         int tl = l / k;
21         map<char, int>m;
22         int count = 0;
23         memset(dp, 0, sizeof(dp));
24         for (int i = 0; i < k; i++)
25         {
26             if (!m[s[i]])
27             {
28                 m[s[i]] = 1;
29                 count++;
30             }
31         }
32         for (int i = 0; i < k; i++) dp[0][i] = count;
33         for (int j = 1; j<tl; j++)
34         {
35             m.clear();
36             count = 0;
37             for (int i = 0; i < k; i++)
38             {
39                 if (!m[s[i + j*k]])
40                 {
41                     m[s[i + j*k]] = 1;
42                     count++;
43                 }
44             }
45             for (int i = 0; i < k; i++) dp[j][i] = l;
46             for (int i = 0; i < k; i++)
47             {
48                 for (int l = 0; l < k; l++)
49                 {
50                     if (m[s[l + (j - 1)*k]] && (count == 1 || s[l + (j - 1)*k] != s[i + j*k]))
51                     {//如果j-1段中第l个字母在第j段中出现过，并且第j段中字母种类只有一种或者有多种但最后一个字母不是它
52                         dp[j][i] = min(dp[j][i], dp[j - 1][l] + count - 1);
53                     }
54                     else dp[j][i] = min(dp[j][i], dp[j - 1][l] + count);
55                 }
56             }
57         }
58         int mincount = l;
59         for (int i = 0; i < k; i++) mincount = min(mincount, dp[tl - 1][i]);
60         cout << mincount << endl;
61     }
62     return 0;
63 }

View Code

7、UVa 11825 Hackers’ Crackdown

　　题意：有一个分布式网络，每台电脑都有若干台和它相邻，同时所有电脑都有N种服务运行。现在有个黑客，他想要发送病毒，一台电脑只能植入一种病毒，只有所有电脑都瘫坏才能瘫坏掉一种服务，求其能够干掉的最多的服务种数。

　　思路：2进制状态压缩保存每台电脑的邻接状态，并用2进制来保存每种状态下能攻陷的电脑。dp[i]表示i状态下能干掉的最多的服务数目。dp[i] = max(dp[i], dp[i^j] + 1)。详细见注释

 1 //状压DP
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxst = (1 << 17);
 6 int ini[20];
 7 int cover[maxst];
 8 int dp[maxst];
 9 int main()
10 {
11     int n;
12     int Case = 1;
13     while (~scanf("%d", &n))
14     {
15         if (n == 0) break;
16         for (int i = 0; i < n; i++)
17         {
18             ini[i] = 0|(1<<i);//包括自身
19             int m;
20             scanf("%d", &m);
21             for (int j = 0; j < m; j++)
22             {
23                 int k;
24                 scanf("%d", &k);
25                 ini[i] |= (1 << k);//加上邻居
26             }
27         }
28         int total = (1 << n) - 1;//总状态数
29         for (int i = 0; i <=total; i++)
30         {
31             cover[i] = 0;
32             for (int j = 0; j < n; j++)
33             {
34                 if (i&(1 << j))//如果该状态能够瘫坏第j台电脑
35                 {
36                     cover[i] |= ini[j];//那么也能瘫坏其邻接的电脑
37                 }
38             }
39         }
40         dp[0] = 0;
41         for (int i = 1; i <= total; i++)
42         {
43             dp[i] = 0;
44             //枚举子集
45             for (int j = i; j > 0; j = (j - 1)&i)
46             {
47                 if (cover[j] == total)//如果子集的状态下能够干掉所有的电脑
48                 {
49                     dp[i] = max(dp[i], dp[i^j] + 1);//那么该状态的能够关闭的服务为max{该状态下能最多关闭的服务数,该状态i和能够干掉所有的电脑的子集的补集所能能关闭的方案数+1（这个1由该子集j提供）}
50                 }
51             }
52         }
53         printf("Case %d: %d
",Case, dp[total]);
54         Case++;
55     }
56     return 0;
57 }

View Code

8、UVA-10635 Prince and Princess

　　题意：求两个序列的公共最长子序列。

　　思路：听说最长公共子序列算法会超时……由于序列每个数都不同，可以转换为求b的最长递增子序列，只需将a数组按顺序从1开始重新编号，建立映射。

 1 #include<iostream>
 2 #include<map>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxl = 300 * 300;
 7 int numa[maxl];
 8 int numb[maxl];
 9 map<int, int>m;
10 void exchange(int x, vector<int>&v)
11 {
12     vector<int>::iterator it;
13     it = lower_bound(v.begin(), v.end(), x);
14     int p = it - v.begin();
15     v[p] = x;
16 }
17 
18 int main()
19 {
20     int t;
21     int Case = 1;
22     scanf("%d", &t);
23     while (t--)
24     {
25         int n, p, q;
26         scanf("%d%d%d", &n, &p, &q);
27         for (int i = 0; i < p+1; i++)
28         {
29             scanf("%d", &numa[i]);
30             m[numa[i]] = i + 1;
31         }
32         for (int i = 0; i < q+1; i++)
33         {
34             scanf("%d", &numb[i]);
35             if (m[numb[i]]) numb[i] = m[numb[i]];
36             else numb[i] = 0;
37         }
38         vector<int>minlen;
39         minlen.push_back(numb[0]);
40         for (int i = 1; i < q+1; i++)
41         {
42             if (numb[i] > minlen.back()) minlen.push_back(numb[i]);
43             else
44             {
45                 exchange(numb[i], minlen);
46             }
47         }
48         printf("Case %d: %d
",Case, minlen.size());
49         Case++;
50     }
51     return 0;
52 }

View Code

9、Uva-10891-Game of Sum

　　题意：A和B两个人，每次可以轮流从一个数组的左端或右端开始拿走若干个数字，直到数组为空，A先手。求最优选择下A能比B最多高出多少。

　　思路：DP，dp[st][ed] = sum[ed] - sum[st - 1] - min(0,L[st][ed - 1],R[st + 1][ed]),L[st][ed] = min(L[st][ed - 1], dp[st][ed]);R[st][ed] = min(R[st + 1][ed], dp[st][ed]).

 1 #include<cstdio>
 2 #include<string>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 typedef long long ll;
 9 const int INF = 0x3f3f3f3f;
10 const int maxn = 100;
11 int n;
12 //const int maxV=12;
13 int a[maxn + 10];
14 int dp[maxn + 5][maxn + 5];
15 int L[maxn + 5][maxn + 5], R[maxn + 5][maxn + 5];
16 int sum[maxn + 10];
17 int main()
18 {
19     while (~scanf("%d", &n) && n)
20     {
21         for (int i = 1; i <= n; i++)
22             scanf("%d", &a[i]);
23         sum[0] = 0;
24         for (int i = 1; i <= n; i++)
25         {
26             dp[i][i] = a[i];//dp[st][ed]表示[st,ed]区间，先手最多得分。
27             sum[i] = sum[i - 1] + a[i];//L[st,ed]=min{dp[st][k]  } ;(st<=k<=ed)
28             L[i][i] = R[i][i] = dp[i][i];//R[st,ed]=min{dp[k][ed]};(st<=k<=ed)
29         }
30         for (int add = 1; add<n; add++)
31         {
32             for (int st = 1; st + add <= n; st++)
33             {
34                 int ed = st + add;
35                 int m = 0;              //m表示此阶段的后手最少能拿多少
36                 m = min(m, L[st][ed - 1]);//表示从右边拿起
37                 m = min(m, R[st + 1][ed]);//表示从左边拿起
38                 dp[st][ed] = sum[ed] - sum[st - 1] - m;
39                 L[st][ed] = min(L[st][ed - 1], dp[st][ed]);
40                 R[st][ed] = min(R[st + 1][ed], dp[st][ed]);
41             }
42         }
43         printf("%d
", dp[1][n] - (sum[n] - sum[0] - dp[1][n]));
44     }
45     return 0;
46 }

View Code

10、Uva 10859 - Placing Lampposts

　　题意：在一张图中，选择结点放置路灯，路灯会照亮连接该结点的路径，问使所有路径都能被照到的最小路灯数目为多少？同时在所有最小的方案中，要保证至少被两盏灯照亮的道路最多。

　　思路：树形DP。优化：x=M*v1+v2，其中M是比"比v2的最大理论值和v2的最小理论值之差"还要大的数。v1表示放置的路灯数目尽可能小，v2表示被一盏灯照亮的路尽可能小。v1=x/M,v2=x%M,v3=m-v2.(被两盏灯照亮的路)。每放一盏灯 + 2000(m)（因为边的最大数量为1000），每增加1条照亮一次的边 + 1.

　　①节点i处不放街灯，那么i是根或者父亲节点放了街灯。所以dp(i,j)=sum{ dp(v,0) | v取遍i的所有儿子节点 }，如果i不是根节点，那么结果+1，因为i和父亲连接的这条边只被一盏灯照亮。

　　②节点i处放街灯，dp(i, j) = sum{ dp(v,1) | v取遍i的所有儿子节点 } +M，如果i不是根节点而且j = 0，那么结果 + 1。

 1 //树形DP
 2 //f(i,j)表示第i盏灯的父亲是否点亮所以j=0|1如果父亲放了，那么自己放或者不放都可以那么f(i,j)=max{∑f(ison,0)∑f(ison,1)}，如果父亲没有放置，那么自己必须放那么f(i,0)=∑f(ison,1)但是这个时候要让被灯照亮两次的边尽量多，那么应该让被照亮一次的边尽量的少，那么另m=n×x+yx代表覆盖当前的子树的灯的数量，y代表当前子树中覆盖完成的最少的被照亮一次的边的数量前提是让y的最大值小于n那么这样x就成为了首要重要的权值，y是次要的然后dp方程改一下
 3 
 4 //f(i, 0) = (∑f(ison, 1)) + 1
 5 //加1是因为自己和自己的父亲又有一条边被照亮一次所以加1，
 6 //f(i, 1) = max{ (∑f(ison,0)) + 1,∑f(ison,1) }
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<cmath>
11 #include<algorithm>
12 #include<string>
13 #include<vector>
14 #include<queue>
15 #include<stack>
16 #define INF 0x3f3f3f3f
17 #define NODENUM 1005
18 #define EDGENUM 1005
19 #define MAXN 1005
20 using namespace std;
21 //优化x=M*v1+v2，其中M是比"比v2的最大理论值和v2的最小理论值之差"还要大的数。v1表示放置的路灯数目尽可能小，v2表示被一盏灯照亮的路尽可能小。v1=x/M,v2=x%M,v3=m-v2.(被两盏灯照亮的路)
22 int root;
23 const int m = 2000;//即理论的M
24 
25 struct EdgeNode
26 {
27     int to, next;
28 } E[2 * EDGENUM];
29 int edgenum, head[NODENUM], N, T, M;
30 bool vis[NODENUM];
31 int ans;
32 int dp[NODENUM][2];//[0]表示不放灯，[1]表示放灯
33 
34 void init()
35 {
36     edgenum = 0;//路条数为0
37     memset(head, -1, sizeof(head));
38     memset(vis, 0, sizeof(vis));
39     ans = 0;
40 }
41 
42 void add(int x, int y)
43 {
44     edgenum++;
45     E[edgenum].next = head[x];
46     head[x] = edgenum;
47     E[edgenum].to = y;
48 }
49 
50 void dfs(int s)
51 {
52     vis[s] = 1;
53     int sum0 = 0, sum1 = 0;
54 
55     for (int p = head[s]; p != -1; p = E[p].next)
56     {
57         int v = E[p].to;
58         if (!vis[v])
59         {
60             dfs(v);
61             sum0 += dp[v][0];
62             sum1 += dp[v][1];
63         }
64     }
65     if (s == root) dp[s][0] = min(sum1 + m, sum0), ans += dp[s][0];
66     else dp[s][1] = min(sum0 + 1, sum1 + m), dp[s][0] = sum1 + m + 1;
67 }
68 //每放一盏灯 + 2000(m)（因为边的最大数量为1000），每增加1条照亮一次的边 + 1.
69 //决策一：节点i处不放街灯，那么i是根或者父亲节点放了街灯。所以dp(i,j)=sum{ dp(v,0) | v取遍i的所有儿子节点 }，如果i不是根节点，那么结果+1，因为i和父亲连接的这条边只被一盏灯照亮。
70 //决策二：节点i处放街灯，dp(i, j) = sum{ dp(v,1) | v取遍i的所有儿子节点 } +M，如果i不是根节点而且j = 0，那么结果 + 1。
71 void build()
72 {
73     scanf("%d%d", &N, &M);
74     for (int i = 0; i<M; ++i)
75     {
76         int a, b;
77         scanf("%d%d", &a, &b);
78         add(a, b);//无向边
79         add(b, a);
80     }
81 }
82 
83 int main()
84 {
85     scanf("%d", &T);//测试用例
86     while (T--)
87     {
88         init();
89         build();
90         for (int i = 0; i<N; ++i) if (!vis[i]) dfs(root = i);//可能有多颗树
91         printf("%d %d %d
", ans / m, M - ans%m, ans%m);
92     }
93     return 0;
94 }

View Code

11、uva 10817 Headmaster's Headache ( 状态压缩dp+sstream应用)

　　题意：学校现在招老师，给出原来任职的老师和前来应聘的老师的信息，求在保证每门科目至少有两个老师教的情况下，最小花费是多少。

　　思路：把学科的信息用二进制状态压缩，s1对应还需要一个老师教的科目,s2对应已经足够老师教的科目.状态设为dp[i][s1][s2]：代表到第i个老师为止，校长最少需要花多少钱达到目标。当i < m 时，我们必须选择，状态只能更新为添加老师，当i >= m时，就可以更新为选或不选老师两种状态。s1：当某个学科还需要1个老师教时，该位记为1，否则记为0；s2:当某个学科已经有足够的老师教时，该位记为1，否则记为0。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<string>
 4 #include<sstream>
 5 #include<algorithm>
 6 using namespace std;
 7 const int INF = 0x7f7f7f7f, MAXN = 131;
 8 int s, m, n, teach[MAXN], cost[MAXN], dp[MAXN][1 << 8][1 << 8];
 9 
10 int DP(int i, int s1, int s2)//s1对应还需要一个老师教的科目,s2对应已经足够老师教的科目.状态设为dp[i][s1][s2]：代表到第i个老师为止，校长最少需要花多少钱达到目标。当i < m 时，我们必须选择，状态只能更新为添加老师，当i >= m时， 就可以更新为选或不选老师两种状态。
11 //s1,s2均为2进制数，每一位表示该课程有无老师
12 //s1：当某个学科还需要1个老师教时，该位记为1，否则记为0
13 //s2:当某个学科已经有足够的老师教时，该位记为1，否则记为0
14 {
15     if (i == m + n) return s2 == (1 << s) - 1 ? 0 : INF;  //每个科目都至少两个老师了，那么就不需要再花钱了
16     int &ret = dp[i][s1][s2];//引用
17     if (ret >= 0) return ret;
18     ret = INF;
19     if (i >= m) ret = DP(i + 1, s1, s2);         //不选
20     s2 |= (s1 & teach[i]);                       //老师能教，并且差一个老师，那么一并运算，剩下的就是满足条件的科目
21     s1 |= teach[i];                              //或上去，没人教的科目肯定变成差一个人教
22     ret = min(ret, cost[i] + DP(i + 1, s1, s2)); //选
23     return ret;
24 }
25 
26 int main()
27 {
28     while (~scanf("%d%d%d",&s,&m,&n))
29     {
30         if (s == 0)break;
31         cin.get();
32         string ss;
33         int x;
34         for (int i = 0; i < m + n; ++i)
35         {
36             getline(cin, ss);
37             stringstream sss(ss);
38             sss >> cost[i];
39             teach[i] = 0;
40             while (sss >> x)
41             {
42                 teach[i] |= 1 << (x - 1);
43             }
44         }
45         memset(dp, -1, sizeof dp);
46         //for (int i = 0; i < m + n; ++i) cout << cost[i] << ':' << teach[i] << endl;
47         cout << DP(0, 0, 0) << '
';
48     }
49     return 0;
50 }

View Code

12、hdu 1024 Max Sum Plus Plus

　　题意：给n个数，现在需要找到m个区间，使得每个区间内元素的和累加起来最大。

　　思路：dp[i][j]表示前j个数在选取第j个数的前提下分成i段的最大值。dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][k]|(0<k<j))+num[j]);dp[i][j-1]+num[j]表示前j-1个分成i组，j放在其他组里；max(dp[i-1][k]|(0<k<j))+num[j]表示前k个分成i-1组的最大值加上第j个独立成组的大小。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,m;
 5 const int maxn = 1000010;
 6 const int INF = 0x7fffffff;
 7 
 8 int num[maxn];
 9 int dp_now[maxn];
10 int max_pre[maxn];
11 //dp[i][j]表示前j个数在选取第j个数的前提下分成i段的最大值。
12 //dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][k]|(0<k<j))+num[j]);
13 //dp[i][j-1]+num[j]表示前j-1个分成i组，j放在其他组里
14 //max(dp[i-1][k]|(0<k<j))+num[j]表示前k个分成i-1组的最大值加上第j个独立成组的大小
15 int main()
16 {
17     while (~scanf("%d%d", &m, &n))
18     {
19         for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
20         memset(dp_now, 0, sizeof(dp_now));
21         memset(max_pre, 0, sizeof(max_pre));
22         int tmax;
23         for (int i = 1; i <= m; i++)
24         {
25             tmax = -INF;
26             for (int j = i; j <= n; j++)
27             {
28                 dp_now[j] = max(dp_now[j - 1]+num[j], max_pre[j - 1] + num[j]);
29                 max_pre[j - 1] = tmax;
30                 tmax = max(tmax, dp_now[j]);
31             }
32         }
33         printf("%d
", tmax);
34     }
35     return 0;
36 }

View Code

13、hdu 1029 Ignatius and the Princess IV

　　题意：给出n个数（n为奇数），输出n个数中至少出现（n+1）/2的数。

　　思路：扫描一边数组即可。

 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;
 6     while (~scanf("%d", &n))
 7     {
 8         int cal = 0;
 9         int m;
10         int t;
11         while (n--)
12         {
13             scanf("%d", &t);
14             if (cal == 0)
15             {
16                 m = t;
17                 cal++;
18             }
19             else
20             {
21                 if(t != m)
22                 {
23                     cal--;
24                 }
25                 else cal++;
26             }
27         }
28         printf("%d
", m);
29     }
30 
31 
32 
33     return 0;
34 }

View Code

14、hdu 1069 Monkey and Banana

　　题意：给出若干种类型的的砖块，其底面的长宽可由任意两边确定。现在把这些砖块叠放，砖块上方的砖块的底面的长和宽都必须小于该砖块的长与宽，求最大高度。

　　思路：先得到各种砖块各种摆放的方式，然后按底面长和宽从大到小排序。从小的开始dp，如果当前块的长和宽比之前的要大，则累加。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 40;
 5 struct node
 6 {
 7     int l;
 8     int w;
 9     int h;
10 }blocks[maxn*6];
11 int dp[maxn * 6];//以i为底的最高高度
12 bool Cmp(const node&a, const node&b)
13 {
14     if (a.l == b.l)return a.w > b.w;
15     else return a.l > b.l;
16 }
17 int main()
18 {
19     int n;
20     int Case = 1;
21     while (~scanf("%d", &n))
22     {
23         if (n == 0)break;
24         int cnt = 0;
25         while (n--)
26         {
27             int xi, yi, zi;
28             scanf("%d%d%d", &xi, &yi, &zi);
29             blocks[cnt].l = xi, blocks[cnt].w = yi, blocks[cnt].h = zi;
30             cnt++;
31             blocks[cnt].l = yi, blocks[cnt].w = xi, blocks[cnt].h = zi;
32             cnt++;
33             blocks[cnt].l = xi, blocks[cnt].w = zi, blocks[cnt].h = yi;
34             cnt++;
35             blocks[cnt].l = zi, blocks[cnt].w = xi, blocks[cnt].h = yi;
36             cnt++;
37             blocks[cnt].l = yi, blocks[cnt].w = zi, blocks[cnt].h = xi;
38             cnt++;
39             blocks[cnt].l = zi, blocks[cnt].w = yi, blocks[cnt].h = xi;
40             cnt++;
41         }
42         sort(blocks, blocks + cnt, Cmp);
43         for (int i = 0; i < cnt; i++) dp[i] = blocks[i].h;
44         for (int i = cnt - 2; i >= 0; --i)
45         {//从小的开始DP
46             for (int j = i + 1; j < cnt; j++)
47             {
48                 if (blocks[j].l < blocks[i].l&&blocks[j].w < blocks[i].w)
49                 {
50                     if (dp[j] + blocks[i].h > dp[i])
51                     {
52                         dp[i] = dp[j] + blocks[i].h;
53                     }
54                 }
55             }
56         }
57         int ans = 0;
58         for (int i = 0; i < cnt; i++)
59         {
60             ans = max(ans, dp[i]);
61         }
62         printf("Case %d: maximum height = %d
", Case++, ans);
63     }
64 
65 
66     return 0;
67 }

View Code

15、hdu 1074 Doing Homework

　　题意：每门功课的作业都有自己的截止日期和做完所需时间。同时，每门功课都有自己学分，如果不能在截止日期前上交作业，每拖一天则多扣一个学分。问最少会扣多少学分。

　　思路：科目最多有15门，枚举每门的完成状态，从小到大枚举，如果当前状态st下,需要完成某项作业j，则考虑其不需完成该作业的状态stt=st^(1<<j),如果加上这门课后其所扣学分更少，则更新，并记录前驱，以便后续输出。

 1 #include<iostream>
 2 #include<stack>
 3 #include<cstdio>
 4 #include<memory.h>
 5 using namespace std;
 6 int n;
 7 const int maxn = 16;
 8 const int INF = 0x7fffffff;
 9 struct sbj
10 {
11     char nm[110];//科目名称
12     int deadline;//截止日期
13     int cost;//完成需花费的时间
14 }homework[maxn];
15 struct node
16 {
17     int tm;
18     int score;
19     int pre;
20     int now;
21 }dp[1 << maxn];
22 int main()
23 {
24     int t;
25     scanf("%d", &t);
26     while (t--)
27     {
28         scanf("%d", &n);
29         {
30             int total = (1 << n) - 1;
31             for (int i = 0; i < n; i++)
32             {
33                 scanf("%s%d%d", homework[i].nm, &homework[i].deadline, &homework[i].cost);
34             }
35             memset(dp, 0, sizeof(dp));
36             for (int st = 1; st <= total; st++)
37             {//从小的枚举
38                 dp[st].score = INF;
39                 for (int j = n - 1; j >= 0; j--)
40                 {//从最后往前枚举
41                     if (st&(1 << j))
42                     {
43                         int st2 = st ^ (1 << j);
44                         int t = dp[st2].tm + homework[j].cost - homework[j].deadline;
45                         if (t < 0) t = 0;
46                         if (t + dp[st2].score < dp[st].score)
47                         {
48                             dp[st].score = t + dp[st2].score;
49                             dp[st].pre = st2;
50                             dp[st].now = j;
51                             dp[st].tm = dp[st2].tm + homework[j].cost;
52                         }
53                     }
54                 }
55             }
56             printf("%d
", dp[total].score);
57             int pre = total;
58             stack<int>s;
59             while (pre)
60             {
61                 s.push(dp[pre].now);
62                 pre = dp[pre].pre;
63             }
64             while (!s.empty())
65             {
66                 printf("%s
", homework[s.top()].nm);
67                 s.pop();
68             }
69         }
70     }
71     return 0;
72 }

View Code

16、hdu 1087 Super Jumping! Jumping! Jumping!

　　题意：现在需要从起点到终点踩格子，每次只能向前踩比当前各自大的数字的格子，求所踩格子的数字之和的最大值。

　　思路：dp[i]代表以第i个数结尾的最大上升子序列的和，对于当前的格子i，遍历之前的dp[j]（0<=j<=i）,如果dp[j]+num[i]>dp[i],则更新dp[i]的值。

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 1010;
 4 int num[maxn];
 5 int dp[maxn];//dp[i]代表以第i个数结尾的最大上升子序列的和
 6 int main()
 7 {
 8     int n;
 9     while (~scanf("%d", &n))
10     {
11         if (n == 0) break;
12         for (int i = 0; i < n; i++) scanf("%d", &num[i]);
13         memset(dp, 0, sizeof(dp));
14         dp[0] = num[0];
15         int ans = dp[0];
16         for (int i = 1; i < n; i++)
17         {
18             dp[i] = num[i];
19             for (int j = 0; j <= i; j++)
20             {
21                 if (num[j] < num[i])
22                 {
23                     if (dp[j] + num[i] > dp[i])
24                     {
25                         dp[i] = dp[j] + num[i];
26                     }
27                 }
28             }
29             if (dp[i] > ans) ans = dp[i];
30         }
31         printf("%d
", ans);
32     }
33     return 0;
34 }

View Code

17、hdu 1114 Piggy-Bank

　　题意：给出空的储钱罐的重量和当前储钱罐的重量，给出n种硬币的重量和面值。求使得储钱罐内的最小的硬币总价值。

　　思路：dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);dp[i]表示硬币总重量为i时，储钱罐内硬币的最低价值。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 510;
 5 const int maxw = 10010;
 6 const int maxp = 50010;
 7 const int INF = 0x7fffffff;
 8 
 9 int dp[maxw];
10 struct coin
11 {
12     int p;
13     int w;
14 }coins[maxn];
15 int main()
16 {
17     int t;
18     scanf("%d", &t);
19     while (t--)
20     {
21         int e, f;
22         scanf("%d%d", &e, &f);
23         int totalw = f - e;//装硬币的重量
24         int minwight = maxw;
25         int n;
26         scanf("%d", &n);
27         for (int i = 0; i < n; i++)
28         {
29             scanf("%d%d", &coins[i].p, &coins[i].w);
30             if (coins[i].w < minwight) minwight = coins[i].w;
31         }
32         if (minwight > totalw)
33         {
34             printf("This is impossible.
");
35             continue;
36         }
37         for (int i = 0; i <= totalw; i++) dp[i] = INF;
38         dp[0] = 0;
39         for (int i = 0; i < n; i++)
40         {
41             for (int v = 0; v <= totalw; v++)
42             {
43                 if (v - coins[i].w >= 0&& dp[v - coins[i].w]!=INF)
44                 {
45                     /*if(dp[v]>=0)dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);
46                     else dp[v] = dp[v - coins[i].w] + coins[i].p;*/
47                     dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);
48                 }
49             }
50         }
51         if(dp[totalw]<INF)printf("The minimum amount of money in the piggy-bank is %d.
", dp[totalw]);
52         else
53         {
54             printf("This is impossible.
");
55         }
56     }
57     return 0;
58 }

View Code

18、HDU 1176 免费馅饼

　　题意：天上开始掉馅饼，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。刚开始时站在5的位置，问最后最多能接住多少馅饼。

　　思路：从最大时间往前DP。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<memory.h>
 4 #include<algorithm>
 5 using namespace std;
 6 int n;
 7 const int maxn = 100010;
 8 const int maxt = 100010;
 9 const int INF = 0x7fffffff;
10 int dp[maxt][12];
11 int main()
12 {
13     while (~scanf("%d", &n))
14     {
15         if (n == 0)break;
16         memset(dp,0, sizeof(dp));
17         int maxtt = 0;
18         for (int i = 0; i < n; i++)
19         {
20             int x, t;
21             scanf("%d%d", &x, &t);
22             dp[t][x]++;
23             if (t > maxtt) maxtt=t;
24         }
25         for (int i = maxtt-1; i >= 0; i--)
26         {
27             for (int st = 0; st <= 10; st++)
28             {
29                 if (st == 0) dp[i][st] += max(dp[i + 1][st], dp[i + 1][st + 1]);
30                 else if(st==10)dp[i][st] += max(dp[i + 1][st], dp[i + 1][st - 1]);
31                 else dp[i][st] += max(dp[i + 1][st - 1], max(dp[i + 1][st], dp[i + 1][st + 1]));
32             }
33         }
34         printf("%d
", dp[0][5]);
35     }
36     return 0;
37 }

View Code