Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

[线性DP][codeforces-1110D.Jongmah]一道花里胡哨的DP题

fanwenlin 2019-02-10 21:18:00 阅读数:115 评论数:0 点赞数:0 收藏数:0

题目来源: 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.由于每一阶段的决策只与上一阶段有关,可以使用滚动数组进行进一步优化。

版权声明
本文为[fanwenlin]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/fanwl/p/10360286.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领