[NOI2004]曼哈顿

第一行有两个正整数m和n，分别表示横向街道和纵向街道的数目。

第二行是一个长度为m的字符串，由北向南列出了m条横向街道改造前的行驶方向。E表示向东，W表示向西。

第三行是一个长度为n的字符串，由西向东列出了n条纵向街道改造前的行驶方向。S表示向南，N表示向北。

第四行有m个非负整数，由北向南列出了改变每条横向街道的行驶方向的工作量。

第五行有n个非负整数，由西向东列出了改变每条纵向街道的行驶方向的工作量。

第六行是一个正整数k，表示游人们提得相对集中的要求的数目。

接下来的k行，每行有四个正整数x1，y1，x2，y2，表示一条要求。这条要求的内容是希望从坐标为(x1,y1)的十字路口到坐标为(x2,y2)的十字路口的最短路径的长度等于这两个路口之间的曼哈顿距离。

第一行是一个字符串，“possible”或者“impossible”（引号不输出）。输出“possible”表示可以通过改变街道的行驶方向满足输入数据中的所有要求，输出“impossible”表示无论怎么设计都不可能满足输入数据中的所有要求。

如果在第一行输出的是“possible”的话，在第二行输出一个整数，表示最小的总工作量，在第三行输出一个长度为m的字符串，由北向南列出改造后的m条横向街道的行驶方向，E表示向东，W表示向西，在第四行输出一个长度为n的字符串，由西向东列出改造后的n条纵向街道的行驶方向，S表示向南，N表示向北。

C++11(clang++ 3.9) 解法, 执行用时: 420ms, 内存消耗: 19148K, 提交时间: 2019-03-23 20:22:29

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=111, maxl = 201, inf = 100000000;
int n, m, K, SM, SN[maxn], r[3], rr[3][maxn], ll[3][maxn], costm[maxn][3], costn[maxn][3];
int sm[maxn], sn[maxn], vm[maxn], vn[maxn], f[maxn][maxl][maxl], pp[maxn][maxl][maxl];
char s[maxn], tm[3], tn[3];
bool g[maxn][maxl][maxl];
struct req { int x1, x2, y1, y2; } a[maxn];
struct inter { int l, r; } in[3][maxl]; 

void init()
{
    scanf("%d%d", &m, &n);
    scanf("%s", s);
    for (int i=1; i<=m; ++i) sm[i] = (s[i-1]=='E');
    scanf("%s", s);
    for (int i=1; i<=n; ++i) sn[i] = (s[i-1]=='S');
    for (int i=1; i<=m; ++i) 
    {
        scanf("%d", vm+i);
        costm[i][sm[i]] = 0, costm[i][1-sm[i]] = vm[i];
    }
    for (int i=1; i<=n; ++i) 
    {
        scanf("%d", vn+i);
        costn[i][sn[i]] = 0, costn[i][1-sn[i]] = vn[i];
    }
    scanf("%d", &K);
    for (int i=1; i<=K; ++i) 
        scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
    tm[0] = 'W', tm[1] = 'E', tn[0] = 'N', tn[1] = 'S';
}

inline bool cmp(const inter &a,const inter &b) 
{ return a.l<b.l || (a.l==b.l && a.r<b.r); }

void maintain()
{
    sort(in[0]+1,in[0]+r[0]+1,cmp);
    sort(in[1]+1,in[1]+r[1]+1,cmp);
    for (int q=0; q<2; ++q)
    {
        for (int i=1; i<=n; ++i)
        {
            int j = 1; ll[q][i] = 1;
            for (; j<=r[q]; ++j)
            if (in[q][j].l>i) break;
            else if (in[q][j].r<i) ll[q][i] = j+1;
            rr[q][i] = j; 
        }
    }
}

void add(int p, int L, int R)
{
    if (L>R) swap(L,R);
    for (int i=1; i<=r[p]; ++i)
        if (L<=in[p][i].l && in[p][i].r<=R) return;
    in[p][++r[p]].l = L, in[p][r[p]].r = R; 
}

bool prepare(int s)
{
    memset(rr, 0 ,sizeof rr);
    memset(ll, 0, sizeof ll);
    r[0] = 0, r[1] = 0;
    for (int i=1; i<=K; ++i)
    {
        int x1 = a[i].x1, y1 = a[i].y1, x2 = a[i].x2, y2 = a[i].y2;
        int p = (x1<x2), q = (y1<y2);
        if (x1!=x2 && y1!=y2)
        {
            if (((s >> (x1-1)) & 1)==q && ((s >> (x2-1)) & 1)==q) add(p,y1,y2); 
            else if (((s >> (x1-1)) & 1)==q) add(p,y2,y2);
            else if (((s >> (x2-1)) & 1)==q) add(p,y1,y1);
            else
            {
                int t = 0, fr=min(x1,x2)+1, en=max(x1,x2);
                for (int j=fr; j<en; ++j)
                    if (((s >> (j-1)) & 1)==q) t = 1;
                if (!t) return 0;
                add(p,y1,y1); add(p,y2,y2);
            }
        }
        else if (x1==x2 && y1!=y2 && ((s >> (x1-1)) & 1) != q) return 0;
        else if (x1!=x2 && y1==y2) add(p,y1,y2);
    }
    maintain();
    return 1;
}

int dp()
{
    memset(f, 0x7, sizeof f);
    f[1][1][1] = 0;
    for (int i=1; i<=n; ++i)
    for (int j=ll[0][i]; j<=rr[0][i]; ++j)
    for (int k=ll[1][i]; k<=rr[1][i]; ++k)
    if (f[i][j][k]<inf)
    {
        if (f[i+1][rr[0][i]][k]>f[i][j][k]+costn[i][0])
        {
            f[i+1][rr[0][i]][k] = f[i][j][k]+costn[i][0];
            g[i+1][rr[0][i]][k] = 0;
            pp[i+1][rr[0][i]][k] = j;
        }
        if (f[i+1][j][rr[1][i]]>f[i][j][k]+costn[i][1])
        {
            f[i+1][j][rr[1][i]] = f[i][j][k]+costn[i][1];
            g[i+1][j][rr[1][i]] = 1;
            pp[i+1][j][rr[1][i]] = k;
        }
    }
    return f[n+1][r[0]+1][r[1]+1];
}

void get_SN(int i, int j, int k)
{
    if (i==1) return;
    SN[i-1] = g[i][j][k];
    if (!g[i][j][k]) get_SN(i-1,pp[i][j][k],k);
    else get_SN(i-1,j,pp[i][j][k]);
}

void work()
{
    int tot = (1<<m), ans = inf;
    for (int i=0; i<tot; ++i)
    {
        int t = 0;
        for (int j=1; j<=m; ++j) t += costm[j][(i>>(j-1))&1];
        if (prepare(i))
        {
            t += dp();
            if (t<ans)
            {
                ans = t, SM = i;
                get_SN(n+1,r[0]+1,r[1]+1);
            }
        }
    }
    if (ans<inf)
    {
        printf("possible\n");
        printf("%d\n", ans);
        while (m--) printf("%c", tm[SM & 1]), SM >>= 1;
        printf("\n");
        for (int i=1; i<=n; ++i)printf("%c", tn[SN[i]]);
        printf("\n");
    } else printf("impossible\n");
}

int main()
{
    init();
    work();
    return 0;
}

详情