都写了三份了，实在不想加重以前随笔的负担
所以只好另起炉灶。
F：Face Formations这道题据说是组合数学的题，但是我是用动态规划作的
上windows实在听不进课，就在草稿纸上胡写乱画，莫名其妙的模拟出来了
主要我是要填表，状态方程，我不知道该怎么写，我模拟下过程好了：
4
1 2 4 7
1
37 37 22 7
2 0 15 15 6
3 0 0 9 5
4 0 0 4 4
5 0 0 0 3
6 0 0 0 2
7 0 0 0 1
ps: 这个表我的填表过程是从下至上，从右至左
结果是在[1][1]的位置上，我代码实现的时候只开了一个数组，因为并不需要把整个表都存下来
以下是我的代码：
#include<iostream>
#include<algorithm>
using namespace std;
#define Max 35
__int64 num[Max],dice[Max];
bool cmp(__int64 a,__int64 b)
{
return a<b;
}
void solve(int n)
{
__int64 i,j;
for(i=1;i<=dice[n];i++)
num[i]=1;
for(i=n;i>=1;i--)
for(j=dice[i]-1;j>=0;j--)
num[j]+=num[j+1];
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF&&n){
memset(dice,0,sizeof(dice));
memset(num,0,sizeof(num));
for(i=1;i<=n;i++)
scanf("%I64d",&dice[i]);
sort(dice+1,dice+n+1,cmp);
solve(n);
printf("%I64d\n",num[1]);
}
return 0;
}
ps:这道题要Long long
posted on 2008-04-11 00:06
zoyi 阅读(281)
评论(3) 编辑 收藏 引用 所属分类:
acm 、
动态规划 、
比赛总结