首页 > 代码库 > sdut 2840 Best string Orz~ (dp)
sdut 2840 Best string Orz~ (dp)
题目
题意:有n1个o, n2个r, n3个z, n4个~, 求有多少种组合使 组合出来的字符串的任意前缀都满足 o的个数>=r的个数,
r的个数>=z的个数 ……………………
思路:递推,枚举用四重循环控制orz~的个数符合题意, 然后当前个数的orz~等于之前orz~分别少一个推过来的,所以相加上,
注意之前可能orz~的某一个没有。
下面的代码是看了标程之后写出来的。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 #define LL long long 9 10 int main() 11 { 12 int n1, n2, n3, n4; 13 int i1, i2, i3, i4; 14 LL d[11][11][11][11]; 15 d[0][0][0][0] = 1; 16 for(i1 = 0; i1 < 10; i1++) 17 for(i2 = 0; i2 <= i1; i2++) 18 for(i3 = 0; i3 <= i2; i3++) 19 for(i4 = 0; i4 <= i3; i4++) 20 { 21 if(i1) d[i1][i2][i3][i4] += d[i1-1][i2][i3][i4]; 22 if(i2) d[i1][i2][i3][i4] += d[i1][i2-1][i3][i4]; 23 if(i3) d[i1][i2][i3][i4] += d[i1][i2][i3-1][i4]; 24 if(i4) d[i1][i2][i3][i4] += d[i1][i2][i3][i4-1]; 25 } 26 while(cin>>n1>>n2>>n3>>n4) 27 { 28 if(n1==0&&n2==0&&n3==0&&n4==0) break; 29 cout<<d[n1][n2][n3][n4]<<endl; 30 } 31 return 0; 32 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。