博客

acwing-277. 饼干(《算法竞赛进阶指南》)

链接跳转

思路:


这里先得引进:排序不等式

若有两个排好序的数列

顺序相乘的和 >= 杂乱相乘的和 >= 逆序相乘的和

证明:

g[i] >= g[j]

a[i] >= a[j]

a[i] * g[i] + g[j] * a[j] – a[i] * g[j] – a[j] * g[i]

= a[i] * (g[i] – g[j]) – a[j] * (g[i] – g[j])

=(a[i] – a[j]) * ( g[i] – g[j])

>= 0

说明 肯定要让怨气值最大的得到的饼干最大

先按怨气值从大到小排序: 最后分配的饼干数 大小 也肯定会从大到小(可能中间存在等于)

f[i][j]: 前i个孩子分配了j块饼干的怨气值最小的集合

属性: min

状态转移:

考虑第i个孩子是否是分配的1块饼干：

1.是: 枚举前k个孩子也是1块饼干 那么这1块饼干的孩子都会产生 (i – k) * 相应怨气值,这里要注意用前缀和来表示这k个孩子的怨气值, f[i – k][j – k] + (s[i] – s[i – k]) * (i – k);

2.不是，那么 我们对前i个孩子都减一块，递归下去肯定会让最后一个孩子为1块饼干，那么又回到1的情况了。 f[i][j] = f[i][j – i]; （j从小到大，前面的状态肯定都计算过），所以不需要担心递归过程

最后再逆序打印出方案即可(任一一种方案)

初始化: f[0][0] = 0, 前0个孩子分配0个方案所产生的怨气值为0，其他的初始化为一个最大值0x3f3f3f3f

代码:

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 31, M = 5010;

int s[N];
PII g[N];
int ans[N];
int f[N][M];
int n, m;

int main(){
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; ++ i){
        cin >> g[i].first;
        g[i].second = i;
    }
    
    sort(g + 1, g + 1 + n, greater<PII>());
    
    for(int i = 1; i <= n; ++ i) s[i] = s[i - 1] + g[i].first;
    
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j){
            if(j < i) continue;
            
            f[i][j] = f[i][j - i];
            
            for(int k = 1; k <= i; ++ k)
                f[i][j] = min(f[i][j], f[i - k][j - k] + (s[i] - s[i - k]) * (i - k));
        }
        
    cout << f[n][m] << endl;
    
    int i = n, j = m;
    int cnt = 0;
    
    while(i){
        if(f[i][j] == f[i][j - i]) cnt ++, j -= i;
        else{
            for(int k = 1; k <= i; ++ k){
                if(f[i][j] == f[i - k][j - k] + (s[i] - s[i - k]) * (i - k)){
                    for(int x = i; x >= i - k + 1; -- x) ans[g[x].second] = cnt + 1;
                    i -= k;
                    j -= k;
                    break;
                }
            }
        }
    }
    
    for(int i = 1; i <= n; ++ i) cout << ans[i] << ' ';
    cout << endl;
    
    return 0;
}