POJ 1651 Multiplication Puzzle

5097 단어
구간 DP.dp[i][j]는 (i, j) 개구간에서 모두 가져간 최소값을 나타낸다.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int INF=0x7FFFFFFF;
const int maxn=100+10;
int a[maxn];
int dp[maxn][maxn];
int n;

void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=INF;
    for(int i=1;i<=n;i++)
        if(i+2<=n)
            dp[i][i+2]=a[i]*a[i+1]*a[i+2];
}

void work()
{
    for(int i=4;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int st=j,en=st+i-1;
            if(en>n) continue;
            for(int s=st+1;s<=en-1;s++) //a[s]    
            {
                int now=0;
                if(s-st>=2) now=now+dp[st][s];
                if(en-s>=2) now=now+dp[s][en];
                now=now+a[st]*a[s]*a[en];
                dp[st][en]=min(dp[st][en],now);
            }
        }
    }
    printf("%d
",dp[1][n]); } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); init(); work(); } return 0; }

좋은 웹페이지 즐겨찾기