站群建站,网站经营模式,网络系统软件应用与维护,动画制作可以自学吗题意 你有n个数字#xff0c;范围[1, m]#xff0c;你可以选择其中的三个数字构成一个三元组#xff0c;但是这三个数字必须是连续的或者相同的#xff0c;每个数字只能用一次#xff0c;问这n个数字最多构成多少个三元组? 分析 这里想谈一下DP的一个套路#xff0c;捆绑… 题意 你有n个数字范围[1, m]你可以选择其中的三个数字构成一个三元组但是这三个数字必须是连续的或者相同的每个数字只能用一次问这n个数字最多构成多少个三元组? 分析 这里想谈一下DP的一个套路捆绑 有的DP题目它可能会要求和一些东西捆绑求方案数这种时候如何单点设置状态呢 以这个题为例只考虑前i种数字对于数字i,它可能 (i,i,i) (i-2,i-1,i) (i-1,i) (i,) 如果是后两种它还未构成一个合法的序列我们还不知道是否存在i1来完善它 也就是考虑前i种数字的时候后两种不应该被计入方案数里但转移的时候我们要用到他们的数量这里就可以再用两维将他的数量捆绑起来一起转移状态 dp[i][j][k] 表示只考虑前i种数字捆绑了j个(i-1,i) k个(i)的最大方案数初始条件 dp[0][0][0] 0 ,others -inf 因为假设只考虑前0种数字实际不存在假定数量为0),它无法构成任何三元组但是转移到前1种可以用前0种转移过来 其余的都是未求解状态 默认为负无穷转移方案 我们有a[i1]个i1 考虑如何从dp[i][j][k]转移到前i1个去 考虑第一个贪心策略如果有未完成的三元组优先补全它因为如果不补全它便会向后需求这样无论如何也不会让答案更大 所以我们需要用jk个i1 去补全(i-1,i)和(i)这样我们形成了j个(i-1,i,i1)可以计入方案数里以及k个(i,i1) 还剩下a[i1] - j - k个i1 枚举我们捆绑多少个(i1)将剩下的全部变成(i1,i1,i1) 这样转移的方程就确定了 dp[i1][k][t] max ( dp[i1][k][t] , dp[i][j][k] j (a[i1]-j-k-t)/3) 最终答案就是只考虑前m个数字最大的答案 考虑第二个贪心策略如果我们够造了三个顺子他们其实可以重组成三个同花也就是说j,k一定小于3 代码 #includebits/stdc.h
using namespace std;
int n,m;
int a[1000005];
int dp[1000005][3][3];
int main() {ios::sync_with_stdio(false);cin.tie(0);int tmp;cinnm;for(int i1;in;i) {cintmp;a[tmp];}memset(dp,0x80,sizeof(dp));dp[0][0][0] 0;for(int i0;im;i) {for(int j0;j3;j) {for(int k0;k3;k) {int res a[i1] -j - k;for(int t0;t3tres;t) {dp[i1][k][t] max(dp[i1][k][t],dp[i][j][k]j(res-t)/3);}}}}int ans 0 ;for(int i0;i3;i) for(int j0;j3;j) ans max(ans,dp[m][i][j]);coutansendl;}转载于:https://www.cnblogs.com/greenty1208/p/10357533.html
