codeforces 234F Fence (dp)

2251 단어
제목:
n개의 울타리를 주고 빨간색과 녹색을 칠해야 한다.빨간색의 면적은 a를 초과할 수 없고, 녹색의 면적은 b를 초과할 수 없다.모든 울타리의 높이를 주고 너비는 1이다.얻은 가치는 서로 인접한 울타리의 다른 색깔의 면적과 같다.최소의 가치를 구하다.
문제 풀이:
pp[i][2][j] 앞 i개의 울타리, 첫 번째 i개의 울타리를 빨간색으로 칠하여 j 면적의 빨간색 울타리로 얻은 최소 가치.
이 문제는 무선 TL입니다. 입력할 때 시간이 초과되었기 때문에 파일 흐름으로 읽어야 통과할 수 있습니다. 2시간 동안 구덩이를 팠습니다...
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long lld;
const int oo=0x3f3f3f3f;
const lld OO=1e18;
const int Mod=1000000007;
const int maxn=50000+5;
int dp[2][2][maxn];/// i      j          
int h[205];

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int a,b,n;
    scanf("%d %d %d",&n,&a,&b);
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    memset(dp,0x3f,sizeof dp);
    dp[0][1][0]=dp[0][0][0]=0;
    int cur=1,pre=0,w,t;
    for(int i=0;i<n;i++)
    {
        cur^=1;
        pre+=h[i];
        t=min(h[i],h[i+1]);
        memset(dp[cur^1],0x3f,sizeof dp[cur^1]);
        for(int j=0;j<=a&&j<=pre;j++)
        {
            w=j+h[i+1];
            ///     
            if(j+h[i+1]<=a)
            {
                if(dp[cur^1][0][w]>dp[cur][0][j])
                    dp[cur^1][0][w]=dp[cur][0][j];
                if(dp[cur^1][0][w]>dp[cur][1][j]+t)
                    dp[cur^1][0][w]=dp[cur][1][j]+t;

            }
            ///     
            if(pre-j+h[i+1]<=b)
            {
                if(dp[cur^1][1][j]>dp[cur][0][j]+t)
                    dp[cur^1][1][j]=dp[cur][0][j]+t;
                if(dp[cur^1][1][j]>dp[cur][1][j])
                    dp[cur^1][1][j]=dp[cur][1][j];
            }
        }
    }
    int ans=oo;
    pre+=h[n];
    cur^=1;
    for(int i=0;i<=a;i++)
    {
        if(pre-i<=b)
        {
            if(ans>dp[cur][0][i])
                ans=dp[cur][0][i];
            if(ans>dp[cur][1][i])
                ans=dp[cur][1][i];
        }
    }
    if(ans>=oo)
        ans=-1;
    printf("%d
",ans); return 0; }

좋은 웹페이지 즐겨찾기