文章目录

饼干题目描述题解 划分数题目描述题解 参考

饼干

原题链接：https://www.acwing.com/problem/content/279/

题目描述

圣诞老人共有M个饼干，准备全部分给N个孩子。 每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。 如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。 给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。 输入格式 第一行包含两个整数N,M。 第二行包含N个整数表示g1~gN。 输出格式 第一行一个整数表示最小怨气总和。 第二行N个空格隔开的整数表示每个孩子分到的饼干数，若有多种方案，输出任意一种均可。 数据范围 1≤N≤30, N≤M≤5000, 1≤gi≤107 输入样例： 3 20 1 2 3 输出样例： 2 2 9 9

题解

题目求每个小孩的a[i] * g[i]相加最小。运用排序不等式可知g[i]最小乘以a[i]最大相加可以得到总和最小。

#include "iostream" #include "cstring" #include "algorithm" using namespace std; const int N = 35, M = 5010; typedef pair<int, int> PII; int n, m; int f[N][M]; PII g[N]; int s[N]; int ans[N]; int main(){ cin>>n>>m; for(int i = 1; i <= n; i++){ cin >> g[i].first; g[i].second = i; } sort(g + 1, g + n + 1); reverse(g + 1, g + n + 1); for(int i = 1; i <= n; i++) s[i] = s[i-1] + g[i].first; memset(f, 0x3f3f, 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]; //有0个1 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, h = 0; while(i){ if(f[i][j] == f[i][j-i]) j -= i, h++; 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 u = i - k + 1; u <= i; u++) ans[g[u].second] = 1 + h; i -= k; j -= k; break; } } } } for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl; return 0; }

划分数

题目描述

有n个无区别的物品，将他们划分成不超过m组，求出划分方法数模M的余数。 1 <= m <= n <= 1000; 2 <= M <= 10000; Input 输入 n,m,M分别代表n个物品、m个组、对M取模。 Output 输出划分方法数对M取模的余数。

题解

首先设dp[i][j]代表的是j的i划分。这里需要分两种情况进行讨论： 1.j<i：也就是j不够分为i个划分，这时候只能在i当前位置填0，所以就等于dp[i-1][j]的总数了。 2.j>=i：也就是j够分为i个划分，这里也需要分两种情况进行讨论。 -这时候第i个位置填0，所以需要加上dp[i-1][j]的总数 然而为了保证满足i个划分结构，可以先放i个1，这时候就是1,1,1…1保证有i个，然后再加上dp[i][j - i]个划分的总数即可。

#include <iostream> const int N = 1010; int f[N][N]; int main { int n, m, M; cin >> n >> m >> M; f[0][0] = 1; for(int i = 1;i <= m;i++) { for(int j = 0;j <= n;j++) { // 如果当前分数大于i if(j >= i) { f[i][j] = (f[i - 1][j] + f[i][j - i]) % M; } else { dp[i][j] = dp[i - 1][j]; } } } cout << f[n][m] << endl; } }

参考

https://www.acwing.com/solution/content/5240/

https://blog.csdn.net/zzz805/article/details/101615928