sdut 2840 Best string Orz~ (dp)

时间:2022-02-25 16:04:53

题目

题意:有n1个o, n2个r, n3个z, n4个~, 求有多少种组合使 组合出来的字符串的任意前缀都满足 o的个数>=r的个数,

r的个数>=z的个数 ……………………

思路:递推,枚举用四重循环控制orz~的个数符合题意, 然后当前个数的orz~等于之前orz~分别少一个推过来的,所以相加上,

注意之前可能orz~的某一个没有。

下面的代码是看了标程之后写出来的。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL long long int main()
{
int n1, n2, n3, n4;
int i1, i2, i3, i4;
LL d[][][][];
d[][][][] = ;
for(i1 = ; i1 < ; i1++)
for(i2 = ; i2 <= i1; i2++)
for(i3 = ; i3 <= i2; i3++)
for(i4 = ; i4 <= i3; i4++)
{
if(i1) d[i1][i2][i3][i4] += d[i1-][i2][i3][i4];
if(i2) d[i1][i2][i3][i4] += d[i1][i2-][i3][i4];
if(i3) d[i1][i2][i3][i4] += d[i1][i2][i3-][i4];
if(i4) d[i1][i2][i3][i4] += d[i1][i2][i3][i4-];
}
while(cin>>n1>>n2>>n3>>n4)
{
if(n1==&&n2==&&n3==&&n4==) break;
cout<<d[n1][n2][n3][n4]<<endl;
}
return ;
}