啊，这是一道挺不错的动态规划的题目呢。
一开始我们并没有找出规律，后来队友突然喊了一句：“dp啊！” 顿时人生豁然开朗了。。。
于是她很神奇的推出了转移方程，然后再共同查错下，a出了这道题，真是佩服这人的高智商啊
题意：
首先n，代表的是n个人，然后是A,B，分别代表两个门的值。
然后第二行给出了n个人的价值，问你要使这n个人全部进入门中（可以是A,B,或是其中的一扇门），总共有几种方法。
但是要注意这里的价值并不是仅仅加起来就好了，这里是要把它加起来直到为一个个位数。
思路：
定义：dp[i][j]为前i个人中然后取得的价值为j的方案数
状态转移方程：dp[i][j]=dp[i-1][j]+dp[i-1][j-idx[i]] //这里的含义是等于i-1个人取得j的方案数加上i-1个人取得j-idx[i]的方案数，因为这里相当于是01背包，我们在这里是在第i个人的时候才取的idx[i]这个价值。
哦 这里还有一个转移方程： dp[i][j]=dp[i-1][j]+dp[i-1][j+9-idx[i]]//这里的含义是主要是后面那个式子与上面有区别，后面那个意思是：比如说现在你的j=2，然后idx=8，那么你还需要多余的3这个数字，，因为（3+8）%9=2，所以这也算是一种方案数。
第二个转移方程十分重要，也就是这个题的坑点所在！
然后还要分情况：
1）当所有人全部进入到B中去时
2）把人员分配到A与B中去，这里也同时算上了人员全都进入了A的情况。我们最后只需要取一种dp[n][A]就可以了，因为其余的人必定要进入到另一个B中去的。所以方案数就是dp[n][A]
3）当第二种不成立时，那么我们要把人员都分配到A中去。为了计算的方便，我们把第二种不成立的就另外分开来到第三种情况中去。
最后别忘了mod就好。
#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<math.h>using namespace std;#define maxn 100010#define mod 258280327int idx[maxn];int dp[maxn][12];int main(){int T;int n,A,B;scanf("%d",&T);while(T–){scanf("%d%d%d",&n,&A,&B);memset(idx,0,sizeof(idx));memset(dp,0,sizeof(dp));int sum=0;for(int i=1;i<=n;i++){scanf("%d",&idx[i]);sum+=idx[i];}sum=sum%9;int res=0;if(sum==B||sum+9==B) res++;if(sum==(A+B)||(sum+9)==(A+B)||(sum+18)==(A+B)){dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<10;j++){if(j>=idx[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-idx[i]];else dp[i][j]=dp[i-1][j]+dp[i-1][j+9-idx[i]];dp[i][j]=dp[i][j]%mod;}}printf("%d\n",(dp[n][A]+res)%mod);}else{if(sum%A==0) res++;printf("%d\n",res);}}}dp真的是很有趣啊！
继续思考，加油加油！！！！！！
版权声明：本文为博主原创文章，未经博主允许不得转载。
懂得接受失败的人，就是懂得人生真谛的人，
