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[][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=;i<=n;i++)

                for (int j=i+;j<=n;j++)

                        scanf("%d",&tot[i][j]),tot2[j][i]=tot[i][j];

        for (int i=;i<=n;i++)

                for (int j=i+;j<=n;j++)

                        stot[i][j]=stot[i][j-]+tot[i][j];

        for (int i=;i<=n;i++)

                for (int j=;j<i;j++)

                        stot2[i][j]=stot2[i][j-]+tot2[i][j];

        for (int i=;i<MAXN;i++)

                for (int j=;j<MAXN;j++)

                        dp[i][j]=-INF;

        for (int i=;i<=n;i++)

                dp[][i]=;

        for (register int p=;p<=m;p++)

        {

                for (int i=;i<=n;i++)

                {

                        int v=;

                        for (int k=i;k<n;k++)

                        {

                                v+=stot[k][n];

                                v-=stot2[k][k-]-stot2[k][i-];

                                if (dp[p][i]<dp[p-][k+]+v)

                                {

                                        dp[p][i]=dp[p-][k+]+v;

                                        pv[p][i]=k+;

                                }

                        }

                }

        }

        //printf("%d\n",dp[m][1]);

        int cur=;

        for (int i=;i<m-;i++)

        {

                cur=pv[m-i][cur];

                printf("%d ",cur-);

        }

        cur=pv[m-(m-)][cur];

        printf("%d",cur-);

        printf("\n");

}

秒客网