幸運票

題目大意：

一個長度為2N的序列，這些數(shù)的總和為S，當這個序列的前N個和后N個總和相等時，它是符合題意的，問有符合題意的有多少種可能

樣例輸入

2 2

樣例輸出

4

數(shù)據(jù)范圍限制

1<=N<=50

S<=1000

解題思路：

先將S/2得出兩邊的總數(shù)分別是多少，然后再用DP枚舉每一位數(shù)和總和，在經(jīng)過特判，用每一位往后推

#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）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。