愛華網(wǎng)| Time Limit:1000MS | Memory Limit:10000K | |
| Total Submissions:3418 | Accepted:1427 |
Description
Polygon is a game for one player that starts on apolygon with N vertices, like the one in Figure 1, where N=4. Eachvertex is labelled with an integer and each edge is labelled witheither the symbol + (addition) or the symbol * (product). The edgesare numbered from 1 to N.On the first move, one of the edges is removed. Subsequent movesinvolve the following steps:
�pick an edge E and the two vertices V1 and V2 that are linked byE; and
�replace them by a new vertex, labelled with the result ofperforming the operation indicated in E on the labels of V1 andV2.
The game ends when there are no more edges, and its score is thelabel of the single vertex remaining.
Consider the polygon of Figure 1. The player started by removingedge 3. After that, the player picked edge 1, then edge 4, and,finally, edge 2. The score is 0.
Write a program that, given a polygon, computes the highestpossible score and lists all the edges that, if removed on thefirst move, can lead to a game with that score.
Input
Your program is to read from standard input. Theinput describes a polygon with N vertices. It contains two lines.On the first line is the number N. The second line contains thelabels of edges 1, ..., N, interleaved with the vertices' labels(first that of the vertex between edges 1 and 2, then that of thevertex between edges 2 and 3, and so on, until that of the vertexbetween edges N and 1), all separated by one space. An edge labelis either the letter t (representing +) or the letter x(representing *).3 <= N <= 50
For any sequence of moves, vertex labels are in the range[-32768,32767].
Output
Your program is to write to standard output. Onthe first line your program must write the highest score one canget for the input polygon. On the second line it must write thelist of all edges that, if removed on the first move, can lead to agame with that score. Edges must be written in increasing order,separated by one space.Sample Input
4t -7 t 4 x 2 x 5
Sample Output
331 2
Source
IOI1998對著解題報告看了許久才看懂，看來應該總結(jié)一下這幾天做的dp題了
引用：
多邊形游戲
多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點
構(gòu)成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予一
個運算符“+”或“*”。所有邊依次用整數(shù)從1到n編號。
游戲第1步，將一條邊刪除。
隨后n-1步按以下方式操作：
(1)選擇一條邊E以及由E連接著的2個頂點V1和V2；
(2)用一個新的頂點取代邊E以及由E連接著的2個頂點V1和
V2。將由頂點V1和V2的整數(shù)值通過邊E上的運算得到的結(jié)果賦
予新頂點。
最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂
點上的整數(shù)值。
問題:對于給定的多邊形，計算最高得分。
最優(yōu)子結(jié)構(gòu)性質(zhì)
•在所給多邊形中，從頂點i(1≤i≤n)開始，長度為j(鏈中有j個頂
點)的順時針鏈p(i，j) 可表示為v[i]，op[i+1]，…，v[i+j-1]。
•如果這條鏈的最后一次合并運算在op[i+s]處發(fā)生(1≤s≤j-1)，
則可在op[i+s]處將鏈分割為2個子鏈p(i，s)和p(i+s，j-s)。
•設m1是對子鏈p(i，s)的任意一種合并方式得到的值，而a和b
分別是在所有可能的合并中得到的最小值和最大值。m2是
p(i+s，j-s)的任意一種合并方式得到的值，而c和d分別是在所
有可能的合并中得到的最小值和最大值。依此定義有
a≤m1≤b，c≤m2≤d
(1)當op[i+s]='+'時，顯然有a+c≤m≤b+d
(2)當op[i+s]='*'時，有min{ac，ad，bc，bd}≤m≤max{ac，
ad，bc，bd}
•換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值
得到。
code：
state transition equation:
m1=max{f[i][k].max,f[k+1][j].max};
m2=max{f[i][k].min,f[k-1][j].min};
f[i][j].max=max(m1,m2);
f[i][j].max表示從頂點i到頂點j的最大值;
f[i][j].min表示從頂點i到頂點j的最小值;
和矩陣連乘類似 i為起始頂點, j為結(jié)束頂點 (i<=k<j)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define le 51
#define INF 1000000000
typedef struct{
int mn,mx;
}ore;
ore f[le][le];
int ar[le];
char op[le];
int n;
int max(int va,int vb){
returnva>vb?va:vb;
}
int min(int va,int vb){
returnva<vb?va:vb;
}
int cal(int va,int vb,char ch){
if(ch=='t')return va+vb;
else return va*vb;
}
void input(){
char ss[3];
int i;
for(i=0;i<n;i++){
scanf("%s%d",ss,&ar[i]);
op[i]=ss[0];
}
}
void init(){
int i;
for(i=0;i<n;i++)
f[i][i].mn=f[i][i].mx=ar[i];
}
void DP(){
inti,j,k,small,big,p1,p2,len;//len is the length of the train ,that is to saylen is the number of the edges
for(len=1;len<n;len++)
for(i=0;i<n;i++){
big=-INF;small=INF;
j=(i+len)%n;
for(k=0;k<len;k++){
p1=(i+k)%n;
p2=(i+k+1)%n;
small=min(small,cal(f[i][p1].mn,f[p2][j].mn,op[p2]));
small=min(small,cal(f[i][p1].mx,f[p2][j].mx,op[p2]));
big=max(big,cal(f[i][p1].mx,f[p2][j].mx,op[p2]));
big=max(big,cal(f[i][p1].mn,f[p2][j].mn,op[p2]));
}
f[i][j].mn=small;f[i][j].mx=big;
}
}
int getmax(){
int i,j,big=-INF;
for(i=0;i<n;i++){
j=(i+n-1)%n;
if(big<f[i][j].mx)big=f[i][j].mx;
}
return big;
}
void print_path(int big){
int i,j,flag=0;
for(i=0;i<n;i++){
j=(i+n-1)%n;
if(big==f[i][j].mx){
if(flag)putchar(' ');
printf("%d",i+1);
flag=1;
}
}
putchar('n');
}
void deal(){
int ans;
DP();
ans=getmax();
printf("%dn",ans);
print_path(ans);
}
int main(void){
while(scanf("%d",&n)==1){
input();
init();
deal();
}
return 0;
}
