poj 1179 매트릭스 체인 곱하기 괄호

제목: 다각형 게임, N 개의 정점이 있는 다각형, 3 <= N <= 50, 다각형은 N 개의 변이 있고 각 정점마다 숫자(플러스 마이너스 가능), 각 변에'+'번호, 또는'*'번호가 있다.1에서 N 번호까지 먼저 한 변을 선택하여 옮긴 다음에 다음과 같은 조작을 한다. 1 한 변의 E와 변의 E가 연결된 두 개의 정점 V1, V2를 선택한다.2 모서리 E와 V1, V2를 새 정점으로 대체하고, 새 정점의 값은 V1, V2의 값으로 모서리에 표시되는 작업을 수행합니다(더하기 또는 곱하기).마지막에 정점 하나만 남았고 끝이 없을 때 게임이 끝난다.현재 작업은 프로그래밍이 마지막 정점에서 얻을 수 있는 최대 값을 구하고, 출력이 최대 값을 얻을 때, 첫 번째 단계는 옮겨야 하는 변을 구하고, 조건에 맞는 변이 여러 개 있으면, 번호에 따라 작은 변에서 큰 변으로 출력하는 것이다.
사고방식: 매트릭스 곱셈으로 할 수 있고 순환도 비교적 잘 처리되는 것을 발견하고 다각형을 순서대로 한 번 복제하면 된다. 체인 곱셈의 최대 길이는 n을 구하면 된다.그러나 정점의 데이터가 마이너스일 수 있기 때문에 최대값은 마이너스가 플러스일 수 있기 때문에 매트릭스 체인의 최소값을 저장해야 한다.

#include <stdio.h>
#include <string.h>
#define INF 0x3fffffff
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define N 150
int n,op[N],dp[N][N][2],ans[N];//dp    0     ，       
int dd(int x){
    return (x<<1)-1;
}
int computemax(int i,int id,int j){
    if(op[id])
        return max(dp[i][id-1][1] * dp[id][j][1], dp[i][id-1][0]*dp[id][j][0]);
    return dp[i][id-1][1] + dp[id][j][1];
}
int computemin(int i,int id,int j){
    if(op[id])
        return min(min(dp[i][id-1][0]*dp[id][j][1],dp[i][id-1][1]*dp[id][j][0]),dp[i][id-1][0]*dp[id][j][0]);
    return dp[i][id-1][0] + dp[id][j][0];
}
int main(){
    while (scanf("%d
",&n)!=EOF) {
        char ch;
        int i,j,p,k,res = -INF,num=0;
        memset(dp,0,sizeof(dp));
        for(i = 1;i<=n;i++){
            scanf("%c %d ",&ch,&k);
            dp[i][i][0] = dp[i][i][1] = dp[i+n][i+n][0] = dp[i+n][i+n][1] = k;
            if(ch == 't')
                op[i] = op[i+n] = 0;
            else if(ch == 'x')
                op[i] = op[i+n] = 1;
        }
        for(k = 1;k<n;k++)
            for(i = 1;i<=dd(n)-k;i++){
                j = i+k;
                dp[i][j][0] = INF;
                dp[i][j][1] = -INF;
                for(p = i+1;p<=j;p++)
                    dp[i][j][0] = min(dp[i][j][0],computemin(i, p, j)),
                    dp[i][j][1] = max(dp[i][j][1],computemax(i, p, j));
            }
        for(i = 1;i<=n;i++){
            if(dp[i][i+n-1][1] > res){
                res = dp[i][i+n-1][1];
                num = 0;
                ans[num++] = i;
            }else if(dp[i][i+n-1][1] == res)
                ans[num++] = i;
        }
        printf("%d
",res);
        for(i = 0;i<num;i++)
            printf("%d ",ans[i]);
        printf("
");
    }
}