Lflame

【2016/4/22 考题】 TV 动态规划

    题意:有 N 个电视节目,观看第 i 个电视节目时,若观看的上一个节目和它种类相同,则获得 Ai 的愉悦度,否则获得 Bi 的愉悦度。问怎样安排一个顺序使得愉悦度最大,注意不是每一个电视节目都必须观看。

    (N<=600 , 种类数 <= N ,  |Ai|、|Bi| <= 10000)


    Orzzzz考场上怎么想也没有想到怎么做....

    首先处理出对于每个种类 i,分成 j 段(也就是说要选择 j 个 B 值)的最大愉悦度 f[i][j]。这个直接贪心即可得到。

    方案合法的条件是同一种类的段数不超过总段数的一半(上取整),于是我们枚举总段数。再用 dp[i][j] 表示前 i 个种类,分成 j 段的最大愉悦度。

    dp[i][j] 从 dp[i-1][j-k] + f[i][k] 转移过来。即先枚举总段数,再枚举 i,枚举 j,枚举 k。看起来是 O(n^4) 的,但其实所有节目的 k 的总和是 O(n)级别的,所以总复杂度为 O(n^3)。

    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define my_min(a,b) ((a)<(b)?(a):(b))

#define my_max(a,b) ((a)>(b)?(a):(b))

using namespace std;


int n ;

int max_T ;

int T[605] , A[605] , B[605] , f[605][605] , dp[605][605] , sum[605] ;

vector<int> ele[605] ;


// f[i][j] 表示只考虑第 i 个种类,分成 j 段,最大权值


// dp[i][j] 表示考虑前 i 个种类,有 j 段,最大权值


bool cmp(const int &a,const int &b){ return B[a]-my_max(A[a],0) > B[b]-my_max(A[b],0) ; }


void init()

{

for(int i=1;i<=max_T;++i){

int len=(int)ele[i].size() ;

sum[i]=sum[i-1]+len ;

for(int j=0;j<len;++j) if(A[ele[i][j]]>0)f[i][0]+=A[ele[i][j]] ;

sort(ele[i].begin(),ele[i].end(),cmp) ;

for(int j=1;j<=len;++j){

int t=ele[i][j-1] ;

f[i][j]=f[i][j-1]+B[t]-my_max(A[t],0) ;

}

f[i][0]=0 ;

}

}


void solve()

{

int ans=0 ;

for(int limits=1;limits<=n;++limits){

int up=(limits+1)/2 ;

memset(dp,0x8f,sizeof(dp)) ;

dp[0][0]=0 ;

for(int i=1;i<=max_T;++i){

int len=(int)ele[i].size() , sj=my_min(sum[i],limits) ;

for(int j=1;j<=sj;++j){

int sk=my_min(my_min(len,j),up) ;

for(int k=0;k<=sk;++k){

dp[i][j]=my_max(dp[i][j],dp[i-1][j-k]+f[i][k]) ;

}

}

}

ans=my_max(ans,dp[max_T][limits]) ;

}

printf("%d\n",ans) ;

}


int main()

{

freopen("tv.in","r",stdin) ;

freopen("tv.out","w",stdout) ;

scanf("%d",&n) ;

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

scanf("%d%d%d",&T[i],&A[i],&B[i]) ;

ele[T[i]].push_back(i) ;

max_T=max(max_T,T[i]) ;

}

init() ;

solve() ;

return 0 ;

}


评论(2)

热度(1)