首页 > 代码库 > SPOJ 12943. Counting, dp ,巧妙
SPOJ 12943. Counting, dp ,巧妙
Given integers N and M, output in how many ways you can take N distinct positive integers such that sum of those integers is <= M. Since result can be huge, output it modulo 1000000007 (10^9 + 7)
N <= 20
M <= 100000
Input
First line of input is number t, number of test cases. Each test case consists only of 2 numbers N and M, in that order.
Output
Output number aksed in description.
题意:找n个不同的数且和不超过m, 求有多少种方案?
DP
n个数为ai,bi = an-i+1 - an-i, bn = a1.
sum(a[i]) = sum(b[i]*i)
即把问题
n个不同的数且和不超过m
转化为
b[i]>0 且 sum(b[i]*i)<=m
然后设dp[i][j]表示b数组前i项的和为j的方案数。
则:dp[i][j] = dp[i][j-i] + dp[i-1][j-i];
answer = sum(dp[n][j]);(1<=j<=m)
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; const int maxn = 20; const int maxm = 1e5; int dp[maxn+10][maxm+10]; int n, m; int main() { int T; dp[0][0] = 1; for(int i=1; i<=maxn; ++i) for(int j=i; j<=maxm; ++j){ dp[i][j] = dp[i][j-i] + dp[i-1][j-i]; if(dp[i][j]>=mod) dp[i][j] -= mod; } scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); int ans = 0; for(int i=1; i<=m; ++i) { ans += dp[n][i]; if(ans>=mod) ans -= mod; } printf("%d\n", ans); } return 0; }
SPOJ 12943. Counting, dp ,巧妙
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。