Equation

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)

Problem Description Gorwin is very interested in equations. Nowadays she gets an equation like this
x1+x2+x3+?+xn=n, and here 0≤xi≤nfor1≤i≤nxi≤xi+1≤xi+1for1≤i≤n?1
For a certain n, Gorwin wants to know how many combinations of xi satisfies above condition.
For the answer may be very large, you are expected output the result after it modular m.
Input Multi test cases. The first line of the file is an integer T indicates the number of test cases.
In the next T lines, every line contain two integer n,m.

[Technical Specification]
1≤T<20
1≤n≤50000
1≤m≤1000000000
Output For each case output should occupies one line, the output format is Case #id: ans, here id is the data number starting from 1, ans is the result you are expected to output.
See the samples for more details.
Sample Input 2 3 100 5 100
Sample Output Case #1: 2 Case #2: 3

解題思路：這個數列有一個很重要的性質：前一個數比后一個數最多小1，那么我們可以得到xi的取值范圍，xi>=0，這是最小的情況，當xi為等差數列時，這時候的xi可能取到的最大值：1+2+3+...+a=n，即a(a+1) = 2*n，那么a<=sqrt(2*n)；這個時候可以采取動態規劃的思想，dp[i][j]表示前i個數的和為i，最大的那個數為j時有多少種方案。

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;typedef long long LL; const int maxn = 50005; int n,m,dp[320][maxn];int main() {int t,cas = 1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);int k = sqrt(2*n + 0.5);memset(dp,0,sizeof(dp));dp[0][0] = 1;for(int i = 1; i <= n; i++)for(int j = 0; j <= k; j++){if(j > i) continue;dp[j][i] = (dp[j][i] + dp[j][i-j]) % m;if(j - 1 >= 0)dp[j][i] = (dp[j][i] + dp[j-1][i-j]) % m;}int ans = 0;for(int i = 0; i <= k; i++)ans = (ans + dp[i][n]) % m;printf("Case #%d: %d\n",cas++,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5185(dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。