【思维 + DP】AcWing 277. 饼干

思路比较毒瘤新颖的一道 DP！这题进阶指南讲得挺好，可以去看看~。

分析

不难想到越贪婪的孩子需要越多的糖，简单的证明：如果存在两个孩子 \(a,b\)??，\(g[a]>g[b]\)?? 且 \(b\)?? 的糖果数大于 \(a\)?? 的，那么交换她们的糖果数，显然不会影响她们和其它人之间的代价（即怨气值贪婪度乘积和），但她们之间的代价却由 \(g[a]\to g[b]\)??，显然更优。

有了单调这样的好性质，我们先对 \(g[]\) 进行降序排序，DP 似乎变得可做了。

但是，在我们定义 \(f(i, j)\) 为前 \(i\) 个孩子共分配 \(j\) 个糖果的最小代价后，发现并不好统计：我们需要知道前面有多少个孩子比第 \(i\) 个孩子分配的糖果数多，但我们的状态难以刻画。

那么，结合单调性，我们考虑对第 \(i\)? 个孩子分得的糖果数进行分类讨论：

• 糖果数 \(>1\)，那么 \(i\) 的前面当然也是如此，这样的话前 \(i\) 个人的糖果数同时 \(-1\) 代价当然不变，因此我们有

  \[f(i, j) = \min(f(i, j), f(i, j-i)) ~~~~~~~~~~ ① \]

• 糖果数 \(=1\)，那么我们考虑枚举 \(k\)，\(k\) 满足前 \(k\) 个人糖果数 \(>1\)，\([k+1, i]\) 的人糖果数 \(=1\)，有

  \[f(i, j) = min(f(i, j), f(k, j-(i-k)) + k\times \sum_{p=k+1}^i g[p]) ~~~~~~~~~~ ② \]

最后就是记录方案了：我们像平时的套路一样，状态有多少维记录的信息就多少维，所以我们这里可以开一个 \(pair\)? 来存。

• 如果是转移 \(①\)，那么我们就对前 \(i\) 个同时 \(+1\)。
• 否则，我们对 \([k+1, i]\) 同时 \(+1\)。

// Problem: 饼干
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/279/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define x first
#define y second
using pii = pair;
using ll = long long;

inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=35, M=5050;

int n, m;
int g[N];
int f[N][M];
pii pre[N][M];

int res[N];
void print(int x, int y){
	if(!x) return;
	auto [tx, ty]=pre[x][y];
	if(x==tx) rep(i,1,x) res[i]++;
	else rep(i,tx+1,x) res[i]++;
	print(tx, ty);
}

int p[N], rp[N];

int main(){
	cin>>n>>m;
	rep(i,1,n) read(g[i]), p[i]=i;
	sort(p+1, p+1+n, [&](int a, int b){
		return g[a]>g[b];
	});
	rep(i,1,n) rp[p[i]]=i;
	sort(g+1, g+1+n, greater());
	rep(i,1,n) g[i]+=g[i-1];
	
	memset(f, 0x3f, sizeof f);
	f[0][0]=0;
	rep(i,1,n) rep(j,1,m){
		int &res=f[i][j];
		if(j>=i){
			if(f[i][j-i]=i-k){
			if(f[k][j-(i-k)]+k*(g[i]-g[k])