poj 1179 循环dp 类似矩阵连乘

本文主要是介绍poj 1179 循环dp 类似矩阵连乘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<cstdio>
#include<cstring>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define INF 0x3f3f3f3f
int dp1[60][60];
int dp2[60][60];
int main()
{int n;char lo[60][3];int d[60];scanf("%d",&n);for(int i=0;i<n;i++)scanf("%s%d",lo[i],&d[i]);for(int i=0;i<n;i++)dp1[i][i]=dp2[i][i]=d[i];for(int len=1;len<n;len++){for(int i=0;i<n;i++){int tmax=-INF,tmin=INF;int j=(i+len)%n;for(int m=0;m<len;m++){int p1=(i+m)%n;int p2=(i+m+1)%n;if(lo[p2][0]=='t'){tmax=MAX(tmax,dp1[i][p1]+dp1[p2][j]);tmin=MIN(tmin,dp2[i][p1]+dp2[p2][j]);}else{tmax=MAX(tmax,dp1[i][p1]*dp1[p2][j]);tmax=MAX(tmax,dp2[i][p1]*dp2[p2][j]);tmax=MAX(tmax,dp1[i][p1]*dp2[p2][j]);tmax=MAX(tmax,dp2[i][p1]*dp1[p2][j]);tmin=MIN(tmin,dp1[i][p1]*dp1[p2][j]);tmin=MIN(tmin,dp2[i][p1]*dp2[p2][j]);tmin=MIN(tmin,dp1[i][p1]*dp2[p2][j]);tmin=MIN(tmin,dp2[i][p1]*dp1[p2][j]);}}dp1[i][j]=tmax;dp2[i][j]=tmin;}}int res=-INF;for(int i=0;i<n;i++){int j=(i+n-1)%n;res=MAX(res,dp1[i][j]);}printf("%d\n",res);for(int i=0;i<n;i++){int j=(i+n-1)%n;if(res==dp1[i][j])printf("%d ",i+1);}printf("\n");
} 

这篇关于poj 1179 循环dp 类似矩阵连乘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---