CF 254E(从当前向后递推)

E. 宿舍分享
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

一个学期有 n 天.第i天早上Vasya会带 ai kg食物来学校(食物最多放2天,今天和明天).

Vasya 每天吃 v kg 食物.他带来的食物原来够吃,但是Vasya 的 m 个室友会吃他的,编号
1 到 m. 第  j 个室友会在 lj到 rj
天和他一起住且每天吃 fj kg食物.
Vasya 每天可以给同住的人  j  fj kg食物(可以选一些人分).Vasya每一次分食物都要让人吃饱(要不然不厚道).

Vasya 怎样分出最多次食物?

Input

第一行2个整数 n 和 v (1 ≤ n, v ≤ 400).
第2行 n 个整数 a1, a2, …, an (1 ≤ ai ≤ 400), 

第三行一个整数 m (1 ≤ m ≤ 400). 接下来 m 行每行3个整数.第
 j 行为 lj, rj, fj (1 ≤ lj ≤ rj ≤ n, 1 ≤ fj ≤ 400).

Output

第一行输出最多分出食物次数. 接下来 n 行第一行输出第 天分几次.接下来输出当天分的朋友的编号(任意顺序).若有多解任意输出一种.

Sample test(s)
input
4 1
3 2 5 4
3
1 3 2
1 4 1
3 4 2
output
7
1 2
1 2
3 2 1 3
2 2 3

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][MAXV2]={0}; // ith day havv j food left last night,->rat int totlastf[MAXN][MAXV2]={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&lt;=n;i++)
{
    for (int j=0;j&lt;=a[i-1];j++) //昨晚最多留下a[i] food(其它过期) 
    {
        int x=j-v+a[i];  //表示昨天剩下的,吃了v,又多了今天的a[i]
        if (x&lt;0) continue; //一定够吃
        if (f[i+1][TomorrowFood]&lt;f[i][j])
        {
            f[i+1][TomorrowFood]=f[i][j];
            totlastf[i+1][TomorrowFood]=0;
            last _Next_ =j;
        }
        for (int k=1;k&lt;man[i].size();k++)
        {
            x-=man[i][k].first;
            if (x&lt;0) break;
            if (f[i+1][TomorrowFood]&lt;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&lt;=MAXV;j++) 
    if (ans&lt;f[n+1][j]) {ans=f[n+1][j]; now=j; }
cout&lt;&lt;ans&lt;&lt;endl;
solve(n+1,now);
return 0;

}