面倒なDP-BZOJ-1605-[Usaco 2008 Open]Crisis on the Farm牧場危機

Descriptionジョンと彼の乳牛はバンド「裏通り乳牛」を結成し、現在牧場でリハーサルをしている.乳牛たちは山に分かれ、N(1≦N≦1000)の山になっている.それぞれの山には、30匹の乳牛がもう1匹の背中を踏んで、牛の塔になっている.牧場にはM(1≦M≦1000)の高い草の山がある.優れた指揮者として、ジョンは口笛を通じて乳牛たちの移動を指揮することができます.彼の口笛は4つの音があって、それぞれすべての牛塔を東南北西の4つの方向に1格移動させることができます.毎回、牛塔が草むらのある格子に着くと、牛塔の一番上の乳牛は草むらの上に飛び込んで、それ以上降りません.他の乳牛は依然として塔状に草の積み重ねのある格子の中に立っていた.牛の塔が乳牛が1匹しか残っていないとき、この乳牛も草の積み重ねに飛び込んだ.突然、ジョンは驚いて色を失った.隣の家の乳牛が爆発したのだ.ゴロゴロと降ってきた牛乳がジョンの牧場に向かって押し寄せてきて、間もなく牧場を水没させます.ジョンはすぐに行動して、口笛で乳牛たちの命を救わなければなりません.彼は乳牛を指揮してできるだけ多くの草むらに飛び乗って、草むらの乳牛は溺れません.ジョンはK回口笛を吹く機会があります.彼はせいぜいどれだけの乳牛を救うことができますか.最も多く救える乳牛の数と、この数に達するジョンが吹く口笛のシーケンスを計算してください.シーケンスはE,W,S,Nで東西南北を表します.複数のシーケンスが要求に達すれば、出力は文字列として最小です.
Inputの第1行は3つの整数N,M,Kを入力し、その後、N行は各行に1対の整数(Xi,Yi)を入力して牛塔の位置を表し、1<=K<=30の後、M行は各行に1対の整数(Xi,Yi)を入力して1つの草積みの位置.1≦Xi≦1000を表す.1≤Yi≤1000.
Output 1行目は最も多く救える乳牛数を出力.2行目は口笛調子シーケンスを出力する.
Sample Input 3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7
Sample Output Use the ‘east’ whistle three times, at which point the milk floods
the area. Each haystack ends up saving 1 cow.
6
EEE
问题解:この问题は本当にとても面倒で、思想の上でとてもとても考えて、1つのDPプラス方案の出力で、しかしこの问题は前処理にしても最后の方案の出力にしても比较的に面倒で、WAは长い间すべて方案の出力の问题です.まず気をつけたいのはKが30以内なので、その牛の塔に牛がいない場合は考えなくてもいいので、移動デルタ(x)、デルタ(y)の場合、どれだけの牛が芝生小屋に届くかを先に処理してget[x][y]と記入します.そしてdp配列は3次元であり,それぞれx,y,k,すなわちdp[i][j][t]はt回目の移動後,合計移動がi,jの最大重み値(すなわち最大救出牛数)である.したがって、状態遷移方程式:dp[i][j][t]=max(dp[i+1][j][t-1]、dp[i+1][j][t-1]、dp[i][j-1][t-1]、dp[i][j+1][t-1])+get[i][j]を簡単に書くことができる.そうすると、簡単に最高の重みを得ることができます.次は嫌なシナリオ出力で、非常に簡単に複数の解があるため、この問題は辞書順の最小のシナリオを出力することを要求して、それでは私達は東南西北の英語の略語の辞書順がE,N,S,Wであることを知ることができます.我々は逆さまにシナリオを求めるので,W,S,N,Eの順に局所シナリオを計画し,最後に得られるのは辞書順が最小である.処理をしていないところもあり、最後に48 ms走ったので、まだ無理でした.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
int n,m,k;
typedef struct node
{
    int x,y;
} node;
node cow[1005];
bool grass[1005][1005];
int  get[105][105];
int dp[105][105][35];
char Turn(int x,int y)
{
    if(x==-1)
        return 'W';
    if(x==1)
        return 'E';
    if(y==-1)
        return 'S';
    return 'N';
}
int moved[4][2]= {{1,0},{0,1},{0,-1},{-1,0}};
bool check(int x,int y)
{
    if(x<0 || x>1000 || y<0 || y>1000)
        return 0;
    return 1;
}
char pre[105][105][35];
char nn[4]= {'E','N','S','W'};
int main()
{
    int x,y;
    cin >> n >> m >> k;
    int fix=k+1;
    for(int i=0; i<n; i++)
        scanf("%d%d",&cow[i].x,&cow[i].y);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&x,&y);
        grass[x][y]=1;
    }
    for(int i=1; i<=2*k+1; i++)
        for(int j=1; j<=2*k+1; j++)
        {
            if(abs(i-fix)+abs(j-fix)>k)
                continue;
            for(int z=0; z<n; z++)
            {
                x=cow[z].x+i-fix,y=cow[z].y+j-fix;
                if(!check(x,y))
                    continue;
                if(grass[x][y])
                    get[i][j]++;
            }
        }
    int out=0;
    for(int t=1; t<=k; t++)
        for(int i=1; i<=2*k+1; i++)
            for(int j=1; j<=2*k+1; j++)
            {
                int tmp=abs(i-fix)+abs(j-fix);
                if(tmp>t)
                    continue;
                if(tmp==t || (t-tmp)%2==0)
                {
                    dp[i][j][t]=max(max(dp[i-1][j][t-1],dp[i+1][j][t-1]),max(dp[i][j-1][t-1],dp[i][j+1][t-1]))+get[i][j];
                    if(t==k && dp[i][j][t]>=out)
                        out=dp[i][j][t];
                }
            }
    for(int i=1; i<=2*k+1; i++)
        for(int j=1; j<=2*k+1; j++)
            if(dp[i][j][k]==out)
                pre[i][j][k]='F';
    cout << out << endl;
    for(int t=k-1; t>=0; t--)
        for(int i=1; i<=2*k+1; i++)
            for(int j=1; j<=2*k+1; j++)
            {
                int tmp=abs(i-fix)+abs(j-fix);
                if(tmp>t)
                    continue;
                for(int z=3; z>=0; z--)
                    if(dp[i][j][t]+get[i+moved[z][0]][j+moved[z][1]]==dp[i+moved[z][0]][j+moved[z][1]][t+1] && pre[i+moved[z][0]][j+moved[z][1]][t+1]!=0)
                        pre[i][j][t]=nn[z];
            }
    int nowx=fix,nowy=fix;
    for(int i=0; i<k; i++)
    {
        printf("%c",pre[nowx][nowy][i]);
        switch(pre[nowx][nowy][i])
        {
        case 'E':
            nowx++;
            break;
        case 'N':
            nowy++;
            break;
        case 'S':
            nowy--;
            break;
        case 'W':
            nowx--;
            break;
        }
    }
    return 0;
}