营销策划好的网站,苏州seo优化公司,长沙装修公司联系电话,清河网站建设电话题目 分析 分果果题解参考#xff0c;下面是补充https://blog.csdn.net/AC__dream/article/details/129431299 关于状态
设f[i][j][k]表示第i个人取到的最后一个糖果编号是j#xff0c;第i-1个人取到的最后一个糖果编号小于等于k时的最大重量的最小值
关于转移方程 关于 j …题目 分析 分果果题解参考下面是补充https://blog.csdn.net/AC__dream/article/details/129431299 关于状态
设f[i][j][k]表示第i个人取到的最后一个糖果编号是j第i-1个人取到的最后一个糖果编号小于等于k时的最大重量的最小值
关于转移方程 关于 j k 的必然性 区间不包含的必然性 代码
#include bits/stdc.h
using namespace std;const int N 110;int n, m;
int f[N][N][N], a[N], s[N];
bool st[N * N];int main()
{cin n m;for (int i 1; i n; i){cin a[i];s[i] a[i] s[i - 1];for(int j 0; j i; j)st[s[i] - s[j]] 1;}int ans 0x3f3f3f3f;for (int mn 1; mn * m 2 * s[n]; mn){if(!st[mn]) continue;memset(f, 0x3f, sizeof f);f[0][0][0] 0;for (int i 1; i m; i){for (int k 0; k n; k){int p 0; //题解里这里是id不是pfor (int j k; j n; j){if(s[j] mn) continue;while (p k s[j] - s[p] mn) p;if (s[j] - s[p] mn)p--;if(k) f[i][j][k] f[i][j][k - 1];f[i][j][k] min(f[i][j][k], max(f[i - 1][k][p], s[j] - s[p]));}}}ans min(ans, f[m][n][n] - mn);}cout ans;
}
