題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5230

解題思路：

這是一個(gè)整數(shù)劃分的模型：

將n劃分為k個(gè)整數(shù)的劃分?jǐn)?shù)

設(shè)dp[i][j]為將i劃分為j個(gè)整數(shù)的劃分?jǐn)?shù)。

　　(1)?i<j為不可能出現(xiàn)的情況，dp[i][j]=0；

　　(2) 若i=j，有一種情況：i可以劃分為i個(gè)1之和，dp[i][j]=1；

　　(3) 若i>j，可以根據(jù)劃分?jǐn)?shù)中是否含有1分為兩類：若劃分?jǐn)?shù)中含有1，可以使用“截邊法”將j個(gè)劃分分別截去一個(gè)1，把問題轉(zhuǎn)化為i-j的j-1個(gè)劃分?jǐn)?shù)，為dp[i-j][j-1]；?若劃分中不包含1，使用“截邊法”將j個(gè)劃分?jǐn)?shù)的最下面一個(gè)數(shù)截去，將為題轉(zhuǎn)化為求i-j的j個(gè)劃分?jǐn)?shù)，為dp[i-j][j]。所以i>j時(shí)dp[i][j]=dp[i-j][j-1]+dp[i-j][j]。

這道題是一樣的，dp[i][j]表示將i劃分成j個(gè)不同的數(shù)，與上面不同的是，這里當(dāng)i=j時(shí)我們是不處理的，即我們不能出現(xiàn)i=j的情況。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; const int mod = 998244353; int n,L,R,C,dp[2][maxn];int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d%d%d",&n,&C,&L,&R);L -= C,R = min(R-C,n-1);memset(dp,0,sizeof(dp));dp[0][0] = 1;int ans = L <= 0 ? 1 : 0;for(int i = 1; (1 + i) * i / 2 <= R; i++) //枚舉人數(shù){for(int j = (1 + i) * i / 2; j <= R; j++) //枚舉分?jǐn)?shù){dp[i & 1][j] = (dp[i & 1][j - i] + dp[(i - 1) & 1][j - i]) % mod; if(L <= j && j <= R)ans = (ans + dp[i & 1][j]) % mod;}memset(dp[(i - 1) & 1],0,sizeof(dp[(i - 1) & 1])); }printf("%d\n",ans);}return 0; }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。