UVa 348 - Optimal Array Multiplication Sequence

1494 단어
제목 링크: UVa 348 - Optimal Array Multiplication Sequence
최우선 매트릭스 곱하기.
DP의 열거 곱셈 위치.
상태 이동 방정식: dp[x][y]=min(dp[x][y],DP(x,i)+DP(i+1,y)+node[x].x * node[i].y * node[y].y)
어려운 점은 인쇄에 있다. 나는 다른 사람의 코드를 보고서야 썼는데, 매우 정교하다.
#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 10 + 2;
struct Node
{
    int x,y;
};
Node node[MAX_N];
int dp[MAX_N][MAX_N];
int path[MAX_N][MAX_N];
int n;

int DP(int x,int y)
{
    if(dp[x][y])
        return dp[x][y];
    for(int i = x;i < y;i++)
    {
        int temp = DP(x,i) + DP(i + 1,y) + node[x].x * node[i].y * node[y].y;
        if(!dp[x][y] || temp < dp[x][y])
        {
            dp[x][y] = temp;
            path[x][y] = i;
        }
    }
    return dp[x][y];
}
void showPath(int x,int y)
{
    if(x == y)
        cout << "A" << x + 1;
    else
    {
        cout << "(";
        showPath(x,path[x][y]);
        cout << " x ";
        showPath(path[x][y] + 1,y);
        cout << ")";
    }
}
int main()
{
    int num = 0;
    while(cin >> n,n)
    {
        memset(dp,0,sizeof(dp));
        memset(path,0,sizeof(path));
        for(int i = 0;i < n;i++)
            cin >> node[i].x >> node[i].y;
        DP(0,n - 1);
        cout << "Case " << ++num << ": ";;
        showPath(0,n - 1);
        cout << endl;
    }
    return 0;
}

좋은 웹페이지 즐겨찾기