都寫了三份了，實在不想加重以前隨筆的負擔
所以只好另起爐灶。
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 閱讀(307)
評論(3) 編輯 收藏 引用 所屬分類:
acm 、
動態規劃 、
比賽總結