首页 > 代码库 > HDU_5230_DP
HDU_5230_DP
http://acm.hdu.edu.cn/showproblem.php?pid=5230
有初始值c，给你1~n的数，输入c+一些数，使得结果在l~r的范围内，输出方案数，注意每种方案中每个数只能使用一次。
可以直接令l和r减去c，便成了分解l~r内的数，求分解方案。
dp[i][j]表示i个数组成j的方案数，根据j最大值推出i最大值，有状态方程dp[i][j] = dp[i][j-i]+dp[i-1][j-i]推出每一个值，最后求出答案即可。
dp[i][j-i]表示相同数量，但每个数都减去一的方案，另外考虑到该方案可以含有1，也就是dp[i-1][j-i]。
另外注意每次要mod一下，于是有了以下代码。
#include<iostream>#include<cstdio>#include<cstring>#define LL long long#define MOD 998244353using namespace std;LL n,c,l,r,dp[450][100005];int main(){ int T; scanf("%d",&T); while(T--) { LL ans; memset(dp,0,sizeof(dp)); scanf("%d%d%d%d",&n,&c,&l,&r); l -= c; r -= c; if(l) ans = 0; else ans = 1; dp[0][0] = 1; for(int i = 1;i*(i+1)/2 <= r;i++) { for(int j = i*(i+1)/2;j <= r;j++) { dp[i][j] = (dp[i][j-i]+dp[i-1][j-i])%MOD; if(j >= l) { ans = (ans+dp[i][j])%MOD; } } } printf("%lld\n",ans); } return 0;}
然而内存竟然超了，于是改进，使用2个数组轮流交替，得出最终答案。
#include<iostream>#include<cstdio>#include<cstring>#define LL long long#define MOD 998244353using namespace std;LL n,c,l,r,dp[2][100005];int main(){ int T; scanf("%d",&T); while(T--) { LL ans; memset(dp,0,sizeof(dp)); scanf("%d%d%d%d",&n,&c,&l,&r); l -= c; r -= c; if(l) ans = 0; else ans = 1; dp[0][0] = 1; for(int i = 1;i*(i+1)/2 <= r;i++) { for(int j = i*(i+1)/2;j <= r;j++) { dp[i%2][j] = (dp[i%2][j-i]+dp[(i+1)%2][j-i])%MOD; if(j >= l) { ans = (ans+dp[i%2][j])%MOD; } } memset(dp[(i+1)%2],0,sizeof(dp[(i+1)%2])); } printf("%lld\n",ans); } return 0;}
HDU_5230_DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。