首页 > 代码库 > (review)zoj1276 区间dp+路径输出
(review)zoj1276 区间dp+路径输出
【题解】:经典的区间dp,并且记录下了dp的path
因为是递归得到的path,所以递归压栈按从里到外的顺序得到path就可以了
输出嵌套括号部分很好的考察了对栈的理解,和递归执行的顺序。
注意题目输出中有的地方有空格
1 //zoj1276 路径输出用到了栈的思想,比较考验思维 2 #include<iostream> 3 #include<string.h> 4 #include<stdio.h> 5 #define maxn 13 6 using namespace std; 7 int N; 8 int a[maxn],b[maxn],dp[maxn][maxn],path[maxn][maxn]; 9 int cas=0; 10 int DP(int i,int j){ 11 if (dp[i][j]!=-1) return dp[i][j]; 12 if (i==j) return dp[i][j]=0; 13 int M=99999999; 14 for(int k=i;k+1<=j;k++){ 15 int d=DP(i,k)+DP(k+1,j)+a[i]*b[k]*b[j]; 16 if (d<M){ 17 M=d; 18 dp[i][j]=M; 19 path[i][j]=k; 20 } 21 } 22 return dp[i][j]; 23 } 24 void PRINT(int i,int j){ 25 if (i<j) printf("("); 26 if (i==j) { 27 printf("A%d",i); 28 return ; //important 29 } 30 31 PRINT(i,path[i][j]); 32 printf(" x "); 33 PRINT(path[i][j]+1,j); 34 35 if (i<j) printf(")"); 36 37 } 38 int main(){ 39 cas=0; 40 while(~scanf("%d",&N) && N>0){ 41 cas++; 42 for(int i=1;i<=N;i++){ 43 scanf("%d%d",&a[i],&b[i]); 44 } 45 memset(dp,-1,sizeof(dp)); 46 //for(int i=1;i<N;i++) path[i][i+1]=i; 47 printf("Case %d: ",cas); 48 DP(1,N); 49 // cout<<path[2][3]; 50 PRINT(1,N); 51 printf("\n"); 52 53 } 54 return 0; 55 56 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。