HDU 5389 Zero Escape （MUT#8 dp优化）

网友投稿 250 2022-12-02

HDU 5389 Zero Escape （MUT#8 dp优化）

【题目链接】：​​click here~~​​

【题目大意】：

题意：

给出n个人的id，有两个门，每个门有一个标号，我们记作a和b，现在我们要将n个人分成两组，进入两个门中，使得两部分人的标号的和（迭代的求，直至变成一位数，我们姑且叫做求“和”操作~）分别等于a和b，问有多少种分法。

【思路】：比赛的时候还是学弟递推的方程，当时是dp三维dp[i][j]k]:分别表示枚举到第i位，A门，B门的状态，但是一直没想到怎么进一步优化，卡在100n的复杂度了

赛后看了一下题解，（虽然高中生写的题解看了好像也没什么卵用~~）发现其实可以用二维数组解决啊，只要计算所有读入数组的和，和A，B门的比较一下，相等是时候进一步枚举j,否则直接判断和A，B门相等的情况，ans++,最后答案就是ans了，还是太弱了，加油吧！T_T!

代码：

#include #include #include #include #include #include #include #include #define eps 0.00000001#define pi acos(-1,0)#define pr 999983using namespace std;typedef long long LL;const int MOD=258280327;int arr[110000]= {0};int dp[110000][10]= {0};inline LL read(){ int c=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} return c*f;}LL get(LL n){return (n-1)%9+1;}int main(){ LL t,n,A,B; t=read(); while(t--){ LL sum=0; LL ans=0; memset(dp,0,sizeof(dp)); memset(arr,0,sizeof(arr)); n=read();A=read();B=read(); for(int i=1; i<=n; ++i){ /// get the sum of arr[i] arr[i]=read(); arr[i]=get(arr[i]); sum+=arr[i]; } sum=get(sum); LL xx=get(A+B); /// judge the sum and xx if(sum==xx){ dp[1][arr[1]]=1; /// dp[i][j]: 枚举到第i位和为j的方案数 for(int i=2; i<=n; ++i){ for(int j=1; j<=9; ++j){ int k=j-arr[i]; if(k<=0) k+=9; dp[i][j]=(dp[i-1][k]+dp[i-1][j])%MOD; } } ans=(dp[n][A]+dp[n][B])%MOD; printf("%lld\n",ans); } else{ if(sum==A) ans++; if(sum==B) ans++; printf("%lld\n",ans%MOD); } } return 0;}/*Sample Input43 9 11 2 63 9 12 3 35 2 31 1 1 1 19 9 91 2 3 4 5 6 7 8 9Sample Output101060*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：方案
上一篇:2015 Multi-University Training Contest 4
下一篇:解决线程池中ThreadGroup的坑
相关文章

 发表评论

暂时没有评论，来抢沙发吧~