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 阅读(309)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
动态规划