首页 > 代码库 > HDU 5800 To My Girlfriend（单调DP）
HDU 5800 To My Girlfriend（单调DP）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5800
【题目大意】
给出一个容量上限s，f[i][j][k][l][m]表示k和l两个物品不能选，i和j两个物品必选，最终质量为m的方案数。求这些方案数的总和。
【题解】
令dp[i][j][s1][s2]表示前i个物品填了j的体积，有s1个物品选为为必选，s2个物品选为必不选的方案数(0<=s1,s2<=2)，则有转移方程dp[i][j][s1][s2]=dp[i-1][j][s1][s2]+dp[i-1][j-a[i]][s1-1][s2]+dp[i-1][j][s1][s2-1]，边界条件为dp[0][0][0][0]=1，时间复杂度O(NS*3^2)。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define rep(i,n) for(int i=1;i<=n;i++)typedef long long LL;const int N=1005;const LL mod=1e9+7;int a[N],n,s,t,T;LL dp[2][N][3][3],ans;void add(LL &a,LL b){a=a+b;if(a>mod)a-=mod;}int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&s); rep(i,n)scanf("%d",a+i); memset(dp,t=0,sizeof(dp)); dp[0][0][0][0]=1;ans=0; rep(i,n){ t^=1; for(int j=s;j>=0;j--){ for(int u=0;u<3;u++)for(int v=0;v<3;v++){ dp[t][j][u][v]=dp[t^1][j][u][v]; if(j>=a[i])add(dp[t][j][u][v],dp[t^1][j-a[i]][u][v]); if(u&&j>=a[i])add(dp[t][j][u][v],dp[t^1][j-a[i]][u-1][v]); if(v)add(dp[t][j][u][v],dp[t^1][j][u][v-1]); } } }rep(i,s)add(ans,dp[t][i][2][2]); ans=((ans*2)%mod)*2%mod; printf("%lld\n",ans); }return 0;}
HDU 5800 To My Girlfriend（单调DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。