uva 10558 - A Brief Gerrymander （dp之不好理解的题意）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int mp[105][105],a[105][105],line[105],street[105],st[105];
int num[105][105],dp[105][105],prex[105][105];

void presolve()
{
    int i,j,t,now;
    memset(a,0,sizeof(a));
    for(i=1; i<=100; i++)
    {
        for(j=1; j<100;)
        {
            now=j;
            if(mp[i][j]) a[i][now]=1;
            j++;
            while(!line[j])
            {
                if(mp[i][j]) a[i][now]=1;
                j++;
            }
        }
    }
    for(i=1; i<=100; i++)  // 预处理num数组  原理同 | 运算
    {
        memset(st,0,sizeof(st));
        for(j=i+1; j<=100; j++)
        {
            for(int k=1; k<m; k++)
            {
                if(a[j-1][street[k]]) st[street[k]]=1;
            }
            t=0;
            for(int k=1; k<m; k++)
            {
                if(st[street[k]]) t++;
            }
            num[i][j]=t;
        }
    }
}
void output(int x,int y)
{
    if(y==0) return ;
    output(prex[x][y],y-1);
    printf(" %d",x);
}
void solve()
{
    int i,j,t,k1;
    ans=0;
    memset(dp,-INF,sizeof(dp));
    memset(prex,-1,sizeof(prex));
    tot-=2;
    for(i=0; i<=100; i++) dp[i][0]=0;
    for(i=1; i<=100; i++)
    {
        for(j=1; j<=i&&j<=tot; j++)
        {
            for(int k=1; k<i; k++)
            {
                if(dp[i][j]<dp[k][j-1]+num[k][i])
                {
                    dp[i][j]=dp[k][j-1]+num[k][i];
                    prex[i][j]=k;
                }
            }
            if(ans<dp[i][tot]+num[i][100])  // 加上最后一块的选区
            {
                ans=dp[i][tot]+num[i][100];
                k1=i;
            }
        }
    }
    printf("%d 1",tot+2);
    output(k1,tot);
    printf(" 100\n");
}
int main()
{
    int i,j,t;
    while(scanf("%d",&n))
    {
        if(n==-1) break ;
        int x,y;
        memset(mp,0,sizeof(mp));
        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&y,&x);
            mp[x][y]=1;
        }
        scanf("%d",&m);
        memset(line,0,sizeof(line));
        for(i=1; i<=m; i++)
        {
            scanf("%d",&t);
            street[i]=t;
            line[t]=1;
        }
        scanf("%d",&tot);
        if(tot==2)
        {
            printf("2 1 100\n");
            continue ;
        }
        presolve();
        solve();
    }
    return 0;
}