BZOJ 1133 [POI2009]Kon DP

제목:링크 요약

방법: DP

해결:

우선 DP식은 쓰기 쉽다.

f[i][j]를 설정하면 전 i역에서 j번 표를 찾았고 i역에서 조사해야 할 최대 인원수를 나타낸다.

f[i][j]=max(f[k][j-1]+peo[x][y])(k<i&&k<=x<i,y>=i)

이렇게 하면 만약에 우리가 x, y를 매거한다면 O(n^4) 정도의 복잡도에 도달할 수 있다.

그래서 이 부분을 최적화할 생각입니다.

sum[i][j]=\sum{peo[x][y]} & & x<=i, i<y<=j

그래서 f[i][l]=min(f[j][l-3]+sum[i][i+1]--sum[j][i+1])

sum의 업데이트를 주의하십시오.

코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 610
#define K 55
using namespace std;
int n,k;
int sum[N][N];
int peo[N][N];
int pre[N][K];
int f[N][K]; 
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            scanf("%d",&peo[i][j]);
    for(int i=1;i<=n;i++)
    {
        sum[i][n]=sum[i-1][n]+peo[i][n];
        for(int j=n-1;j>=1;j--)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j+1]-sum[i-1][j+1]+peo[i][j];
        }
    }
    memset(f,-1,sizeof(f));
    f[0][0]=0;
    for(int l=1;l<=k;l++)
    {
        for(int i=l;i<n;i++)
        {
            for(int j=l-1;j<=i-1;j++)
            {
                if(f[j][l-1]!=-1)
                {
                    if(f[j][l-1]+sum[i][i+1]-sum[j][i+1]>f[i][l])
                    {
                        f[i][l]=f[j][l-1]+sum[i][i+1]-sum[j][i+1];
                        pre[i][l]=j;
                    }
                }
            }
        }
    }
    int ma=0,no;
    for(int i=k;i<n;i++)
        if(f[i][k]>ma)
            ma=f[i][k],no=i;
    int ans[N];
    int cnt=0;
    while(k)
    {
        ans[++cnt]=no;
        no=pre[no][k];
        k--;
    }
    for(int i=cnt;i>=2;i--)printf("%d ",ans[i]);
    printf("%d
",ans[1]);
}