Dp题，主要推方程。
显然每天从食量最小的贪起。
为了处理食物隔夜问题，多留一维表示昨天剩下的食物。
由于不好求出向前的方程，也不知道终态，所以要从当前向后递推（而非从前面向当前递推，类似矿工食堂的解决方案）
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using namespace std;
#define MAXN (400+10)
#define MAXV (400+10)
#define MAXAi (400+10)
#define MAXM (400+10)
#define TomorrowFood (min(a[i],x))
#define _Next_ [i+1][TomorrowFood]
int n,m,v;
vector <pair< int,int> > man[MAXN]; // ith day jth man eat k food. //pair(j,k)
int a[MAXN]={0};
int f[MAXN][MAXV*2]={0}; // ith day havv j food left last night,->rat
int totlastf[MAXN][MAXV*2]={0}; //昨晚几个人吃
int last[MAXN][MAXV*2]={0}; //昨晚剩多少
int solve(int i,int j)
{
if (i>2) solve(i-1,last[i][j]); //{ n+1->n n->n-1 ... 2->1 } 1->0
cout<<totlastf[i][j];
for (int k=1;k<=totlastf[i][j];k++)
cout<<' '<<man[i-1][k].second;
cout<<endl;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n>>v;
for (int i=1;i<=n;i++){cin>>a[i]; man[i].push_back(make_pair(0,0)); }
cin>>m;
for (int i=1;i<=m;i++)
{
int l,r,fi; cin>>l>>r>>fi; //fi=food in a man
for (int j=l;j<=r;j++)
man[j].push_back(make_pair(fi,i));
}
for (int i=1;i<=n;i++) sort(man[i].begin(),man[i].end());
memset(f,128,sizeof(f));
f[1][0]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=a[i-1];j++) //昨晚最多留下a[i] food(其它过期）
{
int x=j-v+a[i]; //表示昨天剩下的，吃了v，又多了今天的a[i]
if (x<0) continue; //一定够吃
if (f[i+1][TomorrowFood]<f[i][j])
{
f[i+1][TomorrowFood]=f[i][j];
totlastf[i+1][TomorrowFood]=0;
last _Next_ =j;
}
for (int k=1;k<man[i].size();k++)
{
x-=man[i][k].first;
if (x<0) break;
if (f[i+1][TomorrowFood]<f[i][j]+k)
{
f[i+1][TomorrowFood]=f[i][j]+k;
totlastf[i+1][TomorrowFood]=k;
last _Next_ =j;
}
}
}
}
int ans=-1,now;
for (int j=0;j<=MAXV;j++)
if (ans<f[n+1][j]) {ans=f[n+1][j]; now=j; }
cout<<ans<<endl;
solve(n+1,now);
return 0;
}