【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)