【FZU 2177】 ytaaa (dp)

952 단어
【FZU 2177】 ytaaa
n개의 폭약이 연속된 폭약을 폭약봉지로 묶을 수 있는 위력은 묶인 폭약에 (최대 위력-최소 위력)^2
dp수 그룹은 i 전 모든 폭약을 묶은 후 최대 위력을 저장합니다
위력을 f수조에 저장하다
전이 방정식은 dp[i]=max(dp[j]+(Max(f[k])-min(f[k]))^2)(i:1->n j:1->i-1k:j+1->i)
코드는 다음과 같습니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int a[1001];//    
int dp[1001];

int main()
{
    int n,i,j,mn,mx;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        for(i = 1; i <= n; ++i)
        {
            scanf("%d",&a[i]);
            mn = mx = a[i];
            for(j = i; j > 0; --j)
            {
                mn = min(mn,a[j]);//(j~i)    
                mx = max(mx,a[j]);//(j~i)    
                dp[i] = max(dp[j-1]+(mx-mn)*(mx-mn),dp[i]);
            }
        }
        printf("%d
",dp[n]); } return 0; }

좋은 웹페이지 즐겨찾기