题目来源: Codeforces - 1110D
题意：你有n张牌（1，2，3，...，m）你要尽可能多的打出[x,x+1,x+2] 或者[x,x,x]的牌型，问最多能打出多少种牌
思路：
1.三组[x,x+1,x+2]的效果等同于 [x,x,x],[x+1,x+1,x+1],[x+2,x+2,x+2]，所以每种顺子牌型最多打2次（如果多于2次，可以被少于3次的方案替代掉，因此忽略）
2.对于每一种牌，用途只有四种。[i-2,i-1,i], [i-1,i,i+1], [i,i+1,i+2], [i,i,i]
我们可以枚举每张牌在四种用途里分别投入了多少
由简单的容斥原理，我们只需要枚举三种顺子牌型分别有x,y,z组，那么[i,i,i]就有(c[i]-x-y-z)/3组
于是我们就有了线性dp的思路
如果建立dp[maxn][3][3][3]，dp[i][x][y][z]表示在第i阶段，第i张牌用来组成三种牌型分别有x,y,z组的最优结果，有dp[i][x][y][z] = max{dp[i-1][?][x][y]} + z + (c[i] - x - y - z) / 3, ans = max{dp[n][?][0][0])
AC代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 const int maxn = 1e6 + 5; 5 int n; 6 int c[maxn]; 7 int dp[maxn][3][3][3]; 8 int main(){ 9 //freopen("data.in","r",stdin); 10 ios::sync_with_stdio(false); 11 cin.tie(0); 12 int cc,t; 13 cin >> cc >> n; 14 for(int i = 1; i <= cc; i++){ 15 cin >> t; 16 c[t]++; 17 } 18 for(int i = 1; i <= n; i++){ 19 for(int x = 0; x < 3; x++){ 20 for(int y = 0; y < 3; y++){ 21 for(int z = 0; z < 3; z++){ 22 if(x + y + z > c[i])continue; 23 for(int t = 0; t < 3; t++) 24 dp[i][x][y][z] = max(dp[i][x][y][z], dp[i-1][t][x][y] + z + (c[i]-x-y-z)/3); 25 } 26 } 27 } 28 } 29 int ans; 30 for(int t = 0; t < 3; t++){ 31 ans = max(ans, dp[n][t][0][0]); 32 } 33 cout << ans << endl; 34 return 0; 35 }
3.仔细观察上面的代码，我们发现在状态转移过程中，两个方程中都有[x][y]，状态之间的联系太过紧密，可以尝试优化一下
如果建立dp[maxn][3][3]，少了一个维度，dp[i][x][y] 表示有x组[i-1,i,i+1],y组[i,i+1,i+2]时的最优结果，有dp[i][x][y] = max{dp[i-1][?][x] + y + (c[i] - ? - x - y)/3}
AC代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 1e6 + 5; 6 int n; 7 int c[maxn]; 8 int dp[maxn][3][3]; 9 int main(){ 10 //freopen("data.in","r",stdin); 11 ios::sync_with_stdio(false); 12 cin.tie(0); 13 int cc,t; 14 cin >> cc >> n; 15 for(int i = 1; i <= cc; i++){ 16 cin >> t; 17 c[t]++; 18 } 19 for(int i = 1; i <= n; i++){ 20 for(int x = 0; x < 3; x++){ 21 for(int y = 0; y < 3; y++){ 22 for(int z = 0; z < 3; z++){ 23 if(x + y + z > c[i])continue; 24 dp[i][y][z] = max(dp[i][y][z], dp[i-1][x][y] + z + (c[i]-x-y-z)/3); 25 } 26 } 27 } 28 } 29 int ans = dp[n][0][0]; 30 cout << ans << endl; 31 return 0; 32 }
4.由于每一阶段的决策只与上一阶段有关，可以使用滚动数组进行进一步优化。
- 还没有人评论，欢迎说说您的想法！
客服
