1900. Brainwashing Device

http://acm.timus.ru/problem.aspx?space=1&num=1900

题目大意：

有N个车站，相邻车站之间形成一个段，这样就有N-1个段，每个段最多可以放一个洗脑的仪器，这样的话，所有经过这个段（放了仪器）的

人都会开心，我们有K个仪器，问怎么放可以让最多的人快乐

思路：

dp[i][j] 代表第i个仪器放在第j个段上的最优值，更新最优值时，需要枚举上一个仪器放的位置，在知道上一个仪器放的位置的情况下，可以

知道当前位置仪器可以作用到多少人。

注意人数全为0的情况

代码：

#include<iostream>

#include<stack>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<string>

#include<cmath>

using namespace std;

typedef long long ll;

typedef pair<int,int> pp;

const int INF=0x3f3f3f3f;

const int N=503;

int d[N][N];

short int f[N][N];

short int a[N][N];

int b[N][N];

int main()

{

    //freopen("data.in","r",stdin);

    int n,k;

    cin>>n>>k;

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

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

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

    cin>>a[i][j];

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

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

    {

        b[i][j]=b[i-1][j];

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

        b[i][j]-=a[l][i];

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

        b[i][j]+=a[i][l];

    }

    memset(d,-1,sizeof(d));

    d[0][0]=0;

    memset(f,-1,sizeof(f));

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

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

    if(d[i][j]!=-1)

    for(int l=j+1;l<n;++l)

    if(d[i][j]+b[l][j+1]>d[i+1][l])

    {

        d[i+1][l]=d[i][j]+b[l][j+1];

        f[i+1][l]=j;

    }

    int x=k,y,ans=-1;

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

    if(d[k][j]>ans)

    {ans=d[k][j];y=j;}

    vector<int>vt;

    while(x!=0)

    {

        vt.push_back(y);

        y=f[x][y];

        --x;

    }

    sort(vt.begin(),vt.end());

    cout<<ans<<endl;

    for(unsigned int i=0;i<vt.size();++i)

    {

        if(i>0) cout<<" ";

        cout<<vt[i];

    }

    cout<<endl;

    return 0;

}

巴特西

1900. Brainwashing Device

最新文章

热门文章