幸运票

题目大意：

一个长度为2N的序列，这些数的总和为S，当这个序列的前N个和后N个总和相等时，它是符合题意的，问有符合题意的有多少种可能

样例输入

2 2

样例输出

4

数据范围限制

1<=N<=50

S<=1000

解题思路：

先将S/2得出两边的总数分别是多少，然后再用DP枚举每一位数和总和，在经过特判，用每一位往后推

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,s,f[52][1002][102],c[202]; void gzj(int x,int y,int l) {for (int i=1;i<=100;i++)//高精加{f[x][y][i]+=f[x-1][y-l][i];f[x][y][i+1]+=f[x][y][i]/10;f[x][y][i]%=10;} } void gzc() {for (int i=1;i<=100;i++)for (int j=1;j<=100;j++)//高精乘{c[i+j-1]+=f[n][s][i]*f[n][s][j];c[i+j]+=c[i+j-1]/10;c[i+j-1]%=10;} } int main() {freopen("tickets.in","r",stdin);freopen("tickets.out","w",stdout);scanf("%d %d",&n,&s);s/=2;for (int i=1;i<=n;i++)for (int j=0;j<=s;j++)if (j>i*9) continue;//太大了else if (i==1&&j<=9) f[i][j][1]=1;//第一位else for (int k=0;k<=min(j,9);k++) gzj(i,j,k);//高精加gzc();int p=200;while (!c[p]&&p) p--;//高精输出if (!p) printf("0");for (int i=p;i>=1;i--)printf("%d",c[i]);fclose(stdin);fclose(stdout);return 0; }

总结

以上是生活随笔为你收集整理的【DP】【高精】幸运票 （jzoj 2122）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。