HDU 5389 DP

本文主要是介绍HDU 5389 DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出n个人的id，有两个门，每个门有一个标号a个b，现在我们要将n个人分成两组，进入两个门中，使得两部分人的标号的和（迭代的求，直至变成一位数）分别等于a和b，问有多少种分法，也可全进入其中的一扇门

一个数的数字根只和它$mod9$之后的值有关，只要类似背包就能完成人员分配的计算。

注意处理全从a出或者全从b出的情况

#include "stdio.h"
#include "string.h"
const int mod=258280327;
int x[100010],dp[100010][20];int main()
{int t,a,k,b,n,key;scanf("%d",&t);while (t--){scanf("%d%d%d",&n,&a,&b);key=0;for(int i=1;i<=n;i++){scanf("%d",&x[i]);key=(key+x[i])%9;}memset(dp,0,sizeof(dp));dp[0][0]=1;//dp[1][x[1]]=1;for(int i=1;i<=n;i++){for(int j=0;j<=9;j++){k=(x[i]+j)%9;dp[i][j]+=dp[i-1][j];dp[i][k]+=dp[i-1][j];dp[i][j]%=mod;dp[i][k]%=mod;}}int ans=0;k=(a+b)%9;a%=9;b%=9;if(k==key){ans+=dp[n][a];if(a==key)ans--;if (a==0) ans--;}a%=9;b%=9;if(a==key)ans++;if(b==key)ans++;printf("%d\n",ans);}return 0;}

这篇关于HDU 5389 DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---