infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=1179
dp题,写起来还是有一点麻烦。
方法:
用数组num记录各顶点的值,op[i][j]记录点i和点j之间的运算符;
把num数组扩展一倍(类似石子合并的做法),然后枚举起点i(i到n),也就是相当与move掉线段 i-1。注意可
能有负负的正的情况,所以还要记录最大最小值。F[i][j][0] imps min,F[i][j][1] imps max;状态转移方程
F[i][j][]=max{F[i][k][] op F[k+1][j][]}{i=<k<j};
枚举起点i即可;

Source Code

Problem: 1179
User: lovecanon
Memory: 296K
Time: 94MS
Language: C++
Result: Accepted



#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
char op[102][102];
int val[102][102][2],num[102],tmp[4],ans[102],top;
int min(int a,int b){if(a<=b) return a;else return b;}
int max(int a,int b){if(a>=b) return a;else return b;}
int cmp(const void *a,const void *b){
    
return *(int *)a-*(int *)b;
}
int main(){
    
int n,i,j,k,l,m;
    scanf(
"%d",&n);
    scanf(
"%*c%c%*c%d",&op[n][n+1],&num[1]);
    num[n
+1]=num[1];
    
for(i=2;i<=n;i++){
        scanf(
"%*c%c%*c%d",&op[i-1][i],&num[i]);
        op[i
-1+n][i+n]=op[i-1][i];
        num[i
+n]=num[i];
    }
    
/*
    for(i=1;i<=2*n-1;i++)
        printf("%d%c",num[i],op[i][i+1]);
    
*/
    
//pre-process
    memset(val,0,sizeof(val));
    
for(i=1;i<=2*n;i++) val[i][i][0]=val[i][i][1]=num[i];
    
    
int MAX=-100000000;
    top
=0;
    
for(i=1;i<=n;i++){//enumerate the edge moved bettween Vi-1 & Vi
        for(l=1;l<=n-1;l++){//l is the difference bettween j & k
            for(j=i;j<=n+i-1-l;j++){//enumerate the start point j 
                k=j+l;
                
//intervla bettween Vj && Vk
                int max=-100000000,min=100000000;
                
for(m=j;m<k;m++){
                    
int cnt;
                    
if(op[m][m+1]=='x'){// op="*"
                        if(val[j][m][0]<0 || val[j][m][1]<0 || val[m+1][k][0]<0 || val[m+1][k][1]<0){
                            
//由于可能出现负负的正的情况,就比较复杂了,因此
                            
//我直接将4个值排序取大小 
                            tmp[0]=val[j][m][0]*val[m+1][k][0];
                            tmp[
1]=val[j][m][0]*val[m+1][k][1];
                            tmp[
2]=val[j][m][1]*val[m+1][k][0];
                            tmp[
3]=val[j][m][1]*val[m+1][k][1];
                            qsort(tmp,
4,sizeof(tmp[0]),cmp);
                            
if(tmp[0]<min) min=tmp[0];//min 
                            if(tmp[3]>max) max=tmp[3];//max
                        }
                        
else{
                            
if((cnt=val[j][m][0]*val[m+1][k][0])<min) min=cnt;
                            
if((cnt=val[j][m][1]*val[m+1][k][1])>max) max=cnt;
                        }
                    }
                    
else{//op="+"
                        if((cnt=val[j][m][0]+val[m+1][k][0])<min) min=cnt;
                        
if((cnt=val[j][m][1]+val[m+1][k][1])>max) max=cnt;
                    }
                }
//endfor m
                val[j][k][0]=min;
                val[j][k][
1]=max;
            }
//endfor j
        }//endfor l
        
        
//用一个栈保存结果,比较方便 
        if(val[i][i+n-1][1]>MAX){
            MAX
=val[i][i+n-1][1];
            top
=0;
            ans[
++top]=i;
        }
        
else if(val[i][i+n-1][1]==MAX) ans[++top]=i;
        
    }
//endfor i
    printf("%d\n",MAX);
    
for(i=1;i<=top;i++) printf("%d ",ans[i]);
    printf(
"\n");
    
//system("pause");
    return 0;
}

posted on 2008-11-15 13:39 infinity 阅读(633) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理