爱华网| 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对着解题报告看了许久才看懂，看来应该总结一下这几天做的dp题了
引用：
多边形游戏
多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点
构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一
个运算符“+”或“*”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。
随后n-1步按以下方式操作：
(1)选择一条边E以及由E连接着的2个顶点V1和V2；
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和
V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋
予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶
点上的整数值。
问题:对于给定的多边形，计算最高得分。
最优子结构性质
•在所给多边形中，从顶点i(1≤i≤n)开始，长度为j(链中有j个顶
点)的顺时针链p(i，j) 可表示为v[i]，op[i+1]，…，v[i+j-1]。
•如果这条链的最后一次合并运算在op[i+s]处发生(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为结束顶点 (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;
}
