http://202.120.80.191/problem.php?problemid=1238昨業里的一道dp，開始一直不想做，因為聽說是樹形dp，而且又聽說樹形dp很難的呀，于是，我跳過了他，不想做，看都不想看
但是，始終我是要做的，剩余作業里就剩它了，好吧，我看題。
看完題后腦子全是樹，煩吶，于是我找了點資料，突然覺得這不就是個矩陣連乘么，再回想記得好像看過矩陣連乘的原型其實就是個樹型結構。應該說這道題不算難，如果跳不出樹這個框架就會想復雜 。
狀態轉移方程和矩陣連乘是很相似的，不同的是，這道題要求做個前序遍歷。
這個遍歷讓我學到了點東西，就是每次的" "和"\n"的處理
以下是我的代碼，有點冗長，我沒有用記憶化搜索，要慢慢學會迭代寫
#include<iostream>
#define MaxN 31
__int64 num[MaxN][MaxN];
int root[MaxN][MaxN],n,k=0;
void solve()
{
int i,j,r,t;
__int64 tmp;
for(r=2;r<=n;r++)
for(i=1;i<=n-r+1;i++){
j=i+r-1;
num[i][j]=num[i][i]+num[i+1][j];
root[i][j]=i;
for(t=i+1;t<j;t++){
tmp=num[i][t-1]*num[t+1][j]+num[t][t];
if(tmp>num[i][j]){
num[i][j]=tmp;
root[i][j]=t;}
}
tmp=num[i][j-1]+num[j][j];
if(tmp>num[i][j]){
num[i][j]=tmp;
root[i][j]=t;
}
}
}
void print_tree(int fis,int end)
{
if(fis<=end){
if(!k){printf("%d",root[fis][end]);k=1;}
else printf(" %d",root[fis][end]);
print_tree(fis,root[fis][end]-1);
print_tree(root[fis][end]+1,end);
}
}
int main()
{
int i;
memset(num,-1,sizeof(num));
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%I64d",&num[i][i]);
root[i][i]=i;}
solve();
printf("%I64d\n",num[1][n]);
print_tree(1,n);
printf("\n");
return 0;
}下面一道是我昨天心情不好的時候去做的一題，呵呵
discuss里說要用母函數，這個離散學過，手算我都煩吶，用程序寫就更讓我煩，要模擬大數相乘的貌似是，提起大數又讓我想到我還要做的一件事，方格取數阿，要rewrite
#include<iostream>
#define MaxN 100
using namespace std;
int num[MaxN+1][MaxN+1];
void init()
{
int i,j;
for(i=0;i<=MaxN;i++)
num[0][i]=1;
for(i=1;i<=MaxN;i++)
for(j=1;j<=MaxN;j++)
if(i>=j)num[i][j]=num[i-j][j]+num[i][j-1];
else num[i][j]=num[i][i];
}
int main()
{
init();
int N;
while(scanf("%d",&N)!=EOF)
printf("%d\n",num[N][N]);
return 0;
}
慢慢熟悉這種模型的dp
posted on 2008-04-23 17:38
zoyi 閱讀(325)
評論(0) 編輯 收藏 引用 所屬分類:
acm 、
動態規劃