Pipe Fitter and the Fierce Dogs

[JAG Asia 2016]

理解题意之后，就是一个非常傻的DP

然后难在理解题意，理解非法状态

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+2;

int dp[maxn][3];

bool mp[maxn][maxn];

int main(){

    int w,h,k,n;

    scanf("%d%d%d%d",&w,&h,&k,&n);

    for(int i=1,u,v;i<=n;++i){

        scanf("%d%d",&u,&v);

        mp[v][u]=1;

    }

    int sp=(w+1)>>1;

    if(!(w&1)) --w;

    if(k<sp){

        puts("-1");

        return 0;

    }

    k-=sp;

    int all=sp*((h+1)/2-1);

    int ans=0;

    for(int i=3;i<=h;i+=2){

        dp[1][0]=0x3f3f3f3f;

        dp[1][1]=1+mp[i-1][1];

        dp[1][2]=1+mp[i-1][2];

        for(int j=3;j<=w;j+=2){

            dp[j][0]=dp[j-2][2]+mp[i-1][j-1]+1;

            dp[j][1]=min(dp[j-2][0],dp[j-2][1])+mp[i-1][j]+1;

            dp[j][2]=min(dp[j-2][0],dp[j-2][1])+mp[i-1][j+1]+1;

        };

        ans+=min(dp[w][0],dp[w][1])-sp;

    }

    if(ans>=k){

        ans-=k;

        all-=k;

        all+=ans;

        printf("%d\n",all);

    }else{

        all-=k;

        printf("%d\n",max(0,all));

    }

    return 0;

}

巴特西

Pipe Fitter and the Fierce Dogs

Pipe Fitter and the Fierce Dogs

最新文章

热门文章