題意：

給出n個人的id，有兩個門，每個門有一個標號，我們記作a和b，現在我們要將n個人分成兩組，進入兩個門中，使得兩部分人的標號的和（迭代的求，直至變成一位數，我們姑且叫做求“和”操作~）分別等于a和b，問有多少種分法。

思路：

很容易想到，如果能找到滿足題意的解，一定滿足a和b的和等于n個人的標號的和，所以我們只需要判斷n個人的標號組成a的情況有多少（或者只判斷b，一樣），同時還要注意可以把n個人都分給a，或者都分給b，這樣也是滿足的。

具體的細節都在代碼里了，一看應該就能懂~~

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;const int maxn=100005;#define mod 258280327int SUM(int x,int y) {int tmp=x+y;int ans=tmp%9;if(ans==0)return 9;return ans; }int num[maxn]; int dp[maxn][10];int main() {int t;scanf("%d",&t);while(t--){int n,a,b;scanf("%d%d%d",&n,&a,&b);int sum=0;for(int i=1;i<=n;i++){scanf("%d",&num[i]);sum=SUM(sum,num[i]);}memset(dp,0,sizeof dp);dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=9;j++){dp[i][j]+=dp[i-1][j];dp[i][SUM(num[i],j)]+=dp[i-1][j];dp[i][j]%=mod;dp[i][SUM(num[i],j)]%=mod;}}int ans=0;if(SUM(a,b)==sum){ans+=dp[n][a];if(a==sum)ans--;}if(a==sum)ans++;if(b==sum)ans++;printf("%d\n",ans);}return 0; }

總結

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

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