http://acm.pku.edu.cn/JudgeOnline/problem?id=1179
dp題，寫起來還是有一點(diǎn)麻煩。
方法：
用數(shù)組num記錄各頂點(diǎn)的值，op[i][j]記錄點(diǎn)i和點(diǎn)j之間的運(yùn)算符;
把num數(shù)組擴(kuò)展一倍（類似石子合并的做法），然后枚舉起點(diǎn)i(i到n)，也就是相當(dāng)與move掉線段 i-1。注意可
能有負(fù)負(fù)的正的情況，所以還要記錄最大最小值。F[i][j][0] imps min,F[i][j][1] imps max;狀態(tài)轉(zhuǎn)移方程
F[i][j][]=max{F[i][k][] op F[k+1][j][]}{i=<k<j};
枚舉起點(diǎn)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){
//由于可能出現(xiàn)負(fù)負(fù)的正的情況，就比較復(fù)雜了，因此
//我直接將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
//用一個棧保存結(jié)果，比較方便
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;
}