bzoj 1133: [POI2009]Kon dp

1133: [POI2009]Kon

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 242 Solved: 81
[Submit][Status][Discuss]

Description

火车沿途有N个车站，告诉你从每一站到每一站的人数，现在查票员只能查K次票，每次查票可以控制目前在车上的所有乘客的车票。求一个查票方案，使得控制的不同的乘客尽量多。（显然对同一个乘客查票多次是没有意义的，只算一次）

Input

第一行正整数 N K (1≤K＜N≤600， K≤50). 接下来N-1行，第i行第j个数描述第i站上，到第i+j站下的乘客个数。总乘客数≤2*10^9

Output

单调增的K个整数，用空格隔开，表示经过哪些站以后查票。

Sample Input

7 2
2 1 8 2 1 0
3 5 1 0 1
3 1 2 2
3 5 6
3 2
1

Sample Output

2 5

　　还是对这种字典序dp的实现方法非常不熟悉，以后看到字典序首先思考dp方向，然后注意废状态的处理，我由于dp数组最开始没有把状态赋为-INF，从而有些状态由一些废状态转移过来了，wa了很久。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 660
#define INF 0x3f3f3f3f
int dp[55][MAXN];
int tot[MAXN][MAXN];
int stot[MAXN][MAXN];
int tot2[MAXN][MAXN];
int stot2[MAXN][MAXN];
int pv[MAXN][MAXN];

int main()
{
        //freopen("input.txt","r",stdin);
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
                for (int j=i+1;j<=n;j++)
                        scanf("%d",&tot[i][j]),tot2[j][i]=tot[i][j];
        for (int i=1;i<=n;i++)
                for (int j=i+1;j<=n;j++)
                        stot[i][j]=stot[i][j-1]+tot[i][j];
        for (int i=1;i<=n;i++)
                for (int j=1;j<i;j++)
                        stot2[i][j]=stot2[i][j-1]+tot2[i][j];
        for (int i=0;i<MAXN;i++)
                for (int j=0;j<MAXN;j++)
                        dp[i][j]=-INF;
        for (int i=1;i<=n;i++)
                dp[0][i]=0;
        for (register int p=1;p<=m;p++)
        {
                for (int i=1;i<=n;i++)
                {
                        int v=0;
                        for (int k=i;k<n;k++)
                        {
                                v+=stot[k][n];
                                v-=stot2[k][k-1]-stot2[k][i-1];
                                if (dp[p][i]<dp[p-1][k+1]+v)
                                {
                                        dp[p][i]=dp[p-1][k+1]+v;
                                        pv[p][i]=k+1;
                                }
                        }
                }
        }
        //printf("%d
",dp[m][1]);
        int cur=1;
        for (int i=0;i<m-1;i++)
        {
                cur=pv[m-i][cur];
                printf("%d ",cur-1);
        }
        cur=pv[m-(m-1)][cur];
        printf("%d",cur-1);
        printf("
");
}