[POI2009]KON-Ticket Inspector(二维前缀和+DP）

题意

有n个车站，现在有一辆火车从1到n驶过，给出aij代表从i站上车j站下车的人的个数。列车行驶过程中你有K次检票机会，所有当前在车上的人会被检票，问最多能检多少个不同的人的票

（n<=600,k<=50)

题解

一开始没啥思路，然后瞄了一眼题解。看到了前缀和然后就想前缀和的意义。

结果又没什么收获。绝望之际想到我瞄的那一眼，看到矩阵是倒着的，然后就有了思路。

DP也就轻而易举地想出来了。

我们建立以左上为原点的前缀和。

然后sum[i][i+1]表示的就是经过i号站点的人数。

然后dp[i][j]代表前i个车站以第i个车站为第j个选择的车站的最优解。

方程:

dp[i][j]=max（dp[i][j],dp[x][j-1]+sum[i][i+1]-sum[x][i+1]）(0<=x<i)

然后记录dp[i][j]从哪里转移就可以得到答案了。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,k,a[N][N],sum[N][N],dp[N][],ans,num,ans1,ans2[],from[N][];

 int main(){

     scanf("%d%d",&n,&k);

     num=k;

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

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

             scanf("%d",&a[i][j+i]);

         }

     }

 //    for(int i=1;i<=n;i++){

 //        for(int j=1;j<=n;j++){

 //            cout<<a[i][j]<<" ";

 //        }

 //        cout<<endl;

 //    }

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

         for(int j=n;j>=;j--){

             sum[i][j]=sum[i-][j]+sum[i][j+]-sum[i-][j+]+a[i][j];

         }

     }

 //    for(int i=1;i<=n;i++){

 //        for(int j=1;j<=n;j++){

 //            cout<<sum[i][j]<<" ";

 //        }

 //        cout<<endl;

 //    }

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

         for(int j=;j<=k;j++){

             dp[i][j]=-;

         }

     dp[][]=;

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

         for(int j=;j<=min(i,k);j++)

             for(int x=;x<i;x++){

                 if(dp[i][j]<dp[x][j-]+sum[i][i+]-sum[x][i+]){

                     dp[i][j]=dp[x][j-]+sum[i][i+]-sum[x][i+];

                     from[i][j]=x;

                 }

             }

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

         if(ans<dp[i][k]){

             ans1=i;

             ans=dp[i][k];

         }

     }

 //    cout<<ans<<endl;

     while(ans1){

         ans2[num]=ans1;

         ans1=from[ans1][num];

         num--;

     }

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

         printf("%d ",ans2[i]);

     }

     return ;

 }

巴特西

[POI2009]KON-Ticket Inspector(二维前缀和+DP）

最新文章

热门文章