2012-0030
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题目描述写的不够好，抱歉。 这里再简要说明一下各个量的意义，n事件数量，t正常清醒时间，k正常睡眠时间，l极限熬夜长度，si第i件事情的开始时刻，ei第i件事情的结束时刻，vi第i件事情的价值。
每天睡眠者的清醒时间可以是t, t+1, t+2, ..., t+l，对应的睡眠时间依次是k, k+1, k+2, ..., k+l，对应的熬夜惩罚依次是0, -1^2^, -2^2^, ..., -l^2^。(熬夜惩罚对一天只计算一次)
一个dp，f[i][j]表示在i时刻已经清醒了j个时间单位的时候最大的满意度。
这里不妨设|x|=x（x>0），0（x<=0）
转移方程:
f[i][j]=max{f[i - 1][j - 1] - |j - t|^2^ + |j - 1 - t|^2^ , f[s[k]][j - (e[k] - s[k])] + v[k] - |j - t|^2^ + |j - (e[k] - s[k]) - t|^2^ (e[k] == i, j - (e[k] - s[k]) >= 0)} (j > 0)
f[i][0]=max{f[i - k - dt][t + dt](0 <= dt <= l)}(保证下标有意义即可)
边界条件：
f[0][0]=0;
f[0][i]=-∞;(i>0) 也就是无法在0时刻清醒i时间单位。
{{{
/*
* File: Solution.cpp
* Author: Bob
*
* Created on 2012年6月25日, 下午9:37
*/
#include <cstdlib>
#include <cstdio>
#include <cassert>
int const max=10000;
int const maxn=1000;
int const maxt=100;
int const maxk=50;
int const maxl=20;
int const maxv=500;
void swap(int &a, int &b){
int t=a;
a=b;
b=t;
}
int cal(int a){
if(a>0)return a*a; else return 0;
}
void solution(){
int f[max+1][maxt+maxl+1],s[maxn+1],e[maxn+1],v[maxn+1];
int n,t,k,l;
scanf("%d%d%d%d",&n,&t,&k,&l);
assert(n>=0 && n<=maxn);
assert(t>=1 && t<=maxt);
assert(k>=1 && k<=maxk);
assert(l>=0 && l<=maxl);
int maxe=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&s[i],&e[i],&v[i]);
//printf("%d %d %d\n",s[i],e[i],v[i]);
assert(s[i]>=0);
assert(e[i]>s[i] && e[i]<=max);
assert(v[i]>=1 && v[i]<=maxv);
if(e[i]>maxe)maxe=e[i];
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if((e[i]>e[j])||(e[i]==e[j] && s[i]<s[j])){
swap(e[i],e[j]);
swap(s[i],s[j]);
swap(v[i],v[j]);
}
}
}
//for(int i=1;i<n;i++)printf("%d ",e[i]);
//printf("%d %d\n",e[n],maxe);
int p=1;
f[0][0]=0;
for(int i=1;i<=t+l;i++){
f[0][i]=-10000000;
}
int ans=0;
for(int i=1;i<=maxe;i++){
f[i][0]=-10000000;//相当于设置成无法到这一状态
for(int dt=0;dt<=l;dt++){
int tmp=i-k-dt;
if(tmp>=0){
tmp=f[tmp][t+dt];
if(tmp>f[i][0])f[i][0]=tmp;
}
}
if(f[i][0]>ans)ans=f[i][0];
//printf("#%d: %d ",i,f[i][0]);
for(int j=1;j<=t+l;j++){
f[i][j]=f[i-1][j-1]-cal(j-t)+cal(j-t-1);
int tmp=0;//同一时间可能有多个事件结束，用tmpp缓存
for(int tmpp=p;tmpp<=n && e[tmpp]==i && j>=e[tmpp]-s[tmpp];tmpp++){
tmp=f[s[tmpp]][j-(e[tmpp]-s[tmpp])]+v[tmpp]-cal(j-t)+cal(j-(e[tmpp]-s[tmpp])-t); //之前已经计算过的熬夜惩罚要补上
if(tmp>f[i][j])f[i][j]=tmp;
}
//printf("%d ",f[i][j]);
if(f[i][j]>ans)ans=f[i][j];
}
//printf("\n");
while(p<=n && e[p]==i)p++;//该循环结束，将p指向结束时间大于i的事件
}
printf("%d\n",ans);
}
int main() {
int c;
scanf("%d",&c);
for(int i=0;i<c;i++){
solution();
}
return 0;
}
}}}题目描述写的不够好，抱歉。 这里再简要说明一下各个量的意义，n事件数量，t正常清醒时间，k正常睡眠时间，l极限熬夜长度，si第i件事情的开始时刻，ei第i件事情的结束时刻，vi第i件事情的价值。
每天睡眠者的清醒时间可以是t, t+1, t+2, ..., t+l，对应的睡眠时间依次是k, k+1, k+2, ..., k+l，对应的熬夜惩罚依次是0, -12, -22, ..., -l2。(熬夜惩罚对一天只计算一次)
一个dp，f[i][j]表示在i时刻已经清醒了j个时间单位的时候最大的满意度。
这里不妨设|x|=x（x>0），0（x<=0）
转移方程:
f[i][j]=max{f[i - 1][j - 1] - |j - t|2 + |j - 1 - t|2 , f[s[k]][j - (e[k] - s[k])] + v[k] - |j - t|2 + |j - (e[k] - s[k]) - t|2 (e[k] == i, j - (e[k] - s[k]) >= 0)} (j > 0)
f[i][0]=max{f[i - k - dt][t + dt](0 <= dt <= l)}(保证下标有意义即可)
边界条件：
f[0][0]=0;
f[0][i]=-∞;(i>0) 也就是无法在0时刻清醒i时间单位。
/*
* File: Solution.cpp
* Author: Bob
*
* Created on 2012年6月25日, 下午9:37
*/
#include <cstdlib>
#include <cstdio>
#include <cassert>
int const max=10000;
int const maxn=1000;
int const maxt=100;
int const maxk=50;
int const maxl=20;
int const maxv=500;
void swap(int &a, int &b){
int t=a;
a=b;
b=t;
}
int cal(int a){
if(a>0)return a*a; else return 0;
}
void solution(){
int f[max+1][maxt+maxl+1],s[maxn+1],e[maxn+1],v[maxn+1];
int n,t,k,l;
scanf("%d%d%d%d",&n,&t,&k,&l);
assert(n>=0 && n<=maxn);
assert(t>=1 && t<=maxt);
assert(k>=1 && k<=maxk);
assert(l>=0 && l<=maxl);
int maxe=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&s[i],&e[i],&v[i]);
//printf("%d %d %d\n",s[i],e[i],v[i]);
assert(s[i]>=0);
assert(e[i]>s[i] && e[i]<=max);
assert(v[i]>=1 && v[i]<=maxv);
if(e[i]>maxe)maxe=e[i];
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if((e[i]>e[j])||(e[i]==e[j] && s[i]<s[j])){
swap(e[i],e[j]);
swap(s[i],s[j]);
swap(v[i],v[j]);
}
}
}
//for(int i=1;i<n;i++)printf("%d ",e[i]);
//printf("%d %d\n",e[n],maxe);
int p=1;
f[0][0]=0;
for(int i=1;i<=t+l;i++){
f[0][i]=-10000000;
}
int ans=0;
for(int i=1;i<=maxe;i++){
f[i][0]=-10000000;//相当于设置成无法到这一状态
for(int dt=0;dt<=l;dt++){
int tmp=i-k-dt;
if(tmp>=0){
tmp=f[tmp][t+dt];
if(tmp>f[i][0])f[i][0]=tmp;
}
}
if(f[i][0]>ans)ans=f[i][0];
//printf("#%d: %d ",i,f[i][0]);
for(int j=1;j<=t+l;j++){
f[i][j]=f[i-1][j-1]-cal(j-t)+cal(j-t-1);
int tmp=0;//同一时间可能有多个事件结束，用tmpp缓存
for(int tmpp=p;tmpp<=n && e[tmpp]==i && j>=e[tmpp]-s[tmpp];tmpp++){
tmp=f[s[tmpp]][j-(e[tmpp]-s[tmpp])]+v[tmpp]-cal(j-t)+cal(j-(e[tmpp]-s[tmpp])-t); //之前已经计算过的熬夜惩罚要补上
if(tmp>f[i][j])f[i][j]=tmp;
}
//printf("%d ",f[i][j]);
if(f[i][j]>ans)ans=f[i][j];
}
//printf("\n");
while(p<=n && e[p]==i)p++;//该循环结束，将p指向结束时间大于i的事件
}
printf("%d\n",ans);
}
int main() {
int c;
scanf("%d",&c);
for(int i=0;i<c;i++){
solution();
}
return 0;
}