经典的DP,把环断开,f[i][j][0]记录i到j的最小值,f[i][j][1]记录最大值,然后递推计算。记录最小值是因为两个负数乘起来可能得到一个大的正数。


#include <cstdio>
int a[100],b[100],n;
char o[100],p[100];
void init() {
    
int i;
    scanf(
"%d",&n);
    
for (i=0;i<n;i++{
        
char s[10];
        scanf(
"%s%d",s,&b[i]);
        o[i]
=s[0];
    }

}

int move() {
    
int i,j,k,f[100][100][2];
    
for (i=0;i<n;i++for (j=i;j<n;j++{
        f[i][j][
0]=0x7fffffff;
        f[i][j][
1]=-0x7fffffff;
    }

    
for (i=0;i<n;i++) f[i][i][0]=f[i][i][1]=a[i];
    
for (i=n-2;i>=0;i--for (j=i+1;j<n;j++{
        
for (k=i;k<j;k++if (p[k]=='t'{
            f[i][j][
0]<?=f[i][k][0]+f[k+1][j][0];
            f[i][j][
1]>?=f[i][k][1]+f[k+1][j][1];
        }

        
else {
            f[i][j][
0]<?=f[i][k][0]*f[k+1][j][0];
            f[i][j][
0]<?=f[i][k][0]*f[k+1][j][1];
            f[i][j][
0]<?=f[i][k][1]*f[k+1][j][0];
            f[i][j][
1]>?=f[i][k][0]*f[k+1][j][0];
            f[i][j][
1]>?=f[i][k][1]*f[k+1][j][1];
        }

    }

    
return f[0][n-1][1];
}

int main() {
    
int i,j,max=-0x7fffffff,ans[100];
    init();
    
for (i=0;i<n;i++{
        
for (j=0;j<n;j++{
            a[j]
=b[(i+j)%n];
            
if (j<n-1) p[j]=o[(i+j+1)%n];
        }

        ans[i]
=move();
        max
>?=ans[i];
    }

    printf(
"%d\n",max);
    
for (i=0;i<n;i++if (ans[i]==max) printf("%d ",i+1); printf("\n");
    
return 0;
}
posted on 2007-10-05 16:47 Felicia 阅读(593) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理