经典DP. 题目来源：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1179枚举第一次拿走的边，f[i][j][0]记录i到j的最小值，f[i][j][1]记录最大值，然后递推计算。记录最小值是因为两个负数相乘可能得到一个大的正数。见代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=100000000;
int n,max_score,tot,fir_mov[55];
int f[55][55][2],val[55];
char sign[55][55];
void fun(int a[4],int &tmax,int &tmin)
{
sort(a,a+4);
if(a[0]<tmin) tmin=a[0];
if(a[3]>tmax) tmax=a[3];
}
int main()
{
scanf("%d",&n);
int i,j,k,s;
for(i=0;i<n;i++)
{
getchar();
scanf("%c%d",&sign[(i-1+n)%n][i],&val[i]);
}
int max_score=-inf;
tot=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
for(k=0;k<n;k++)
{
f[j][k][0]=inf; //min
f[j][k][1]=-inf; //max
}
for(j=0;j<n;j++)
{
f[j][j][0]=val[j];
f[j][j][1]=val[j];
}
int start=i,end=(i-1+n)%n;
for(j=1;j<=n-1;j++)
for(k=start;(k+j)%n!=(end+1)%n;k=(k+1)%n)
{
int v=(k+j)%n;
int tmax=-inf,tmin=inf;
for(s=k;s!=v;s=(s+1)%n)
{
if(sign[s][(s+1)%n]=='t')
{
if(tmax<f[k][s][1]+f[(s+1)%n][v][1])
tmax=f[k][s][1]+f[(s+1)%n][v][1];
if(tmin>f[k][s][0]+f[(s+1)%n][v][0])
tmin=f[k][s][0]+f[(s+1)%n][v][0];
}
else
{
int a[4];
a[0]=f[k][s][1]*f[(s+1)%n][v][1];
a[1]=f[k][s][0]*f[(s+1)%n][v][0];
a[2]=f[k][s][0]*f[(s+1)%n][v][1];
a[3]=f[k][s][1]*f[(s+1)%n][v][0];
fun(a,tmax,tmin);
}
}
if(f[k][v][0]>tmin) f[k][v][0]=tmin;
if(f[k][v][1]<tmax) f[k][v][1]=tmax;
}
if(max_score==f[start][end][1])
{
fir_mov[tot++]=i+1;
}
else if(max_score<f[start][end][1])
{
tot=0;
max_score=f[start][end][1];
fir_mov[tot++]=i+1;
}
}
printf("%d\n",max_score);
for(i=0;i<tot;i++)
if(i!=tot-1) printf("%d ",fir_mov[i]);
else printf("%d\n",fir_mov[i]);
//system("pause");
return 0;
}
posted on 2010-08-23 18:36
wuxu 阅读(160)
评论(0) 编辑 收藏 引用 所属分类:
动态规划