题意:

有n天,m门课和常数k;

每天上一门课,每门课程有两个属性,最少作业量a,最多作业量b,和难度c。

1<=a<=b<=1e16

c<=100

1<=n<=m<=50 1<=k<=100

要求所有课程的作业量总和最多。

要求除第一天外,其他情况下作业量是前一天加k或者前一天乘k。

输出每天课程的序号,以及该课程应该布置的作业量。

思路:

dp[i][j][k]代表第i门课,第j作业量,第k天的总和。

注意j是相对最少作业量的位移量。

#include<bits/stdc++.h>
using namespace std;
struct st{
int id,c;
unsigned long long a,b,num;
};
bool cmp(st a,st b){
return a.c<b.c;
}
st jilu[];
unsigned long long dp[][][];
int fi[][][],fj[][][];
stack<pair<unsigned long long,int> >ss;
int main()
{
int n,m;
unsigned long long kk;
scanf("%d%d%I64u",&n,&m,&kk);
for(int i=;i<m;i++){
int tmp;
scanf("%I64u%I64u%d",&jilu[i].a,&jilu[i].b,&jilu[i].c);
jilu[i].num=jilu[i].b-jilu[i].a;
jilu[i].id=i+;
}
sort(jilu,jilu+m,cmp);
for(int i=;i<m;i++){
for(int k=;k<=n;k++){
for(int j=;j<=jilu[i].num;j++){
if(i==){
if(k==)
dp[i][j][k]=j+jilu[i].a;
}
else if(k==){
dp[i][j][k]=j+jilu[i].a;
}
else{
long long t=jilu[i].a+j-kk;
for(int w=;w<i;w++){
if(jilu[w].c>=jilu[i].c)break;
if(jilu[w].a>t||jilu[w].b<t)continue;
long long tt=t-jilu[w].a;
if(dp[w][tt][k-]){
if(dp[i][j][k]<jilu[i].a+j+dp[w][tt][k-]){
dp[i][j][k]=jilu[i].a+j+dp[w][tt][k-];
fi[i][j][k]=w;
fj[i][j][k]=tt;
}
}
}
t=jilu[i].a+j;
if(t%kk==){
t/=kk;
for(int w=;w<i;w++){
if(jilu[w].c>=jilu[i].c)break;
if(jilu[w].a>t||jilu[w].b<t)continue;
long long tt=t-jilu[w].a;
if(dp[w][tt][k-]){
if(dp[i][j][k]<jilu[i].a+j+dp[w][tt][k-]){
dp[i][j][k]=jilu[i].a+j+dp[w][tt][k-];
fi[i][j][k]=w;
fj[i][j][k]=tt;
}
}
}
}
}
}
}
}
long long ans=;
int idi,idj;
for(int i=;i<m;i++){
for(int j=;j<=jilu[i].num;j++){
if(ans<dp[i][j][n]){
ans=dp[i][j][n];
idi=i;
idj=j;
}
}
}
if(ans==){
puts("NO");
return ;
}
while(n--){
int n_idi=fi[idi][idj][n+];
int n_idj=fj[idi][idj][n+];
if(n!=)
ss.push(make_pair(dp[idi][idj][n+]-dp[n_idi][n_idj][n],jilu[idi].id));
else
ss.push(make_pair(dp[idi][idj][n+],jilu[idi].id));
idi=n_idi;idj=n_idj;
}
puts("YES");
while(!ss.empty()){
pair<unsigned long long,int>t=ss.top();
ss.pop();
printf("%d %I64u\n",t.second,t.first);
}
}
05-08 15:51