算法-动态规划三
切蛋糕
描述
有一块矩形蛋糕，宽和高分别是整数w、h。现要将其切成m块小蛋糕，每个小蛋糕都必须是矩形、且宽和高均为整数。切蛋糕时，每次切一块蛋糕，将其分成两个矩形蛋糕。请计算：最后得到的m块蛋糕中，最大的那块蛋糕的面积下限。
输入
共有多行，每行表示一个测试案例。
每行是三个用空格分开的整数w, h, m ，其中1 ≤ w, h, m ≤ 20 ， m ≤ wh.
当 w = h = m = 0 时不需要处理，表示输入结束。
输出
每个测试案例的结果占一行，输出一个整数，表示最大蛋糕块的面积下限。
解题思路
设ways(w,h,m)表示宽为w,高为h的蛋糕，被切m刀后，最大的那块蛋糕的面积最小 值
题目就是要求ways(W,H,M-1) 边界条件：
w * h < m + 1 INF
m == 0 w*h
递推式: SV为第一刀竖着切时能得到的最好结果，SH为第一刀横着切时能得到的最好结 果，则ways(w,h,m) = min(SV,SH)
SV = min{ Si, i = 1 ... w-1 }, 其中: Si = 为第一刀左边宽为i的情况下的最好结果
Si = min{ max(ways(i,h,k),ways(w-i,h,m-1-k)), k = 0... m-1 }
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int inf=0x3f3f3f3f; // 定义一个无穷大的常量
int dp[405][25][25]; // 定义一个三维数组，用于存储动态规划的结果
int dfs(int m,int w,int h) // 定义一个递归函数，用于计算最大面积
{
if(dp[m][w][h]!=inf) // 如果dp[m][w][h]已经计算过，则直接返回
return dp[m][w][h];
else if(m==0) // 如果m为0，则返回w*h
return dp[m][w][h]=w*h;
else
{
int ans=inf; // 初始化ans为无穷大
for(int i=1,lim=w/2+1;i<=lim;i++) // 遍历所有可能的宽度
for(int k=0;k<=m-1;k++) // 遍历所有可能的层数
ans=min(ans,max(dfs(k,i,h),dfs(m-1-k,w-i,h))); // 计算最大面积
for(int i=1,lim=h/2+1;i<=lim;i++) // 遍历所有可能的高度
for(int k=0;k<=m-1;k++) // 遍历所有可能的层数
ans=min(ans,max(dfs(k,w,i),dfs(m-1-k,w,h-i))); // 计算最大面积
return dp[m][w][h]=ans; // 返回最大面积
}
}
int main()
{
int w,h,m; // 定义宽度、高度和层数
memset(dp,0x3f,sizeof(dp)); // 将dp数组初始化为无穷大
while(cin>>w>>h>>m && w||h||m) // 循环输入宽度、高度和层数，直到输入为0
cout<<dfs(m,w,h)<<endl; // 输出最大面积
return 0;
}4 4 4
4
4 4 3
6
灌溉草场
在一片草场上:有一条长度为L (1 <= L <= 1,000,000，L为偶数)的线段 。John的N (1 <= N <= 1000) 头奶牛都沿着草场上这条线段吃草，每头牛的活动范围是一个开区间(S,E)，S，E都是整数。不同奶牛的活动范围可以有重叠。
John要在这条线段上安装喷水头灌溉草场。每个喷水头的喷洒半径可以随意调节，调节范围是[A B ](1 <= A <= B <= 1000)，A,B都是整数。要求 线段上的每个整点恰好位于一个喷水头的喷洒范围内 每头奶牛的活动范围要位于一个喷水头的喷洒范围内 任何喷水头的喷洒范围不可越过线段的两端(左端是0,右端是L )
请问，John 最少需要安装多少个喷水头。
输入
第1行：整数N、L。 第2行：整数A、B。 第3到N+2行：每行两个整数S、E (0 <= S < E <= L) ，表示某头牛活动 范围的起点和终点在线段上的坐标(即到线段起点的距离)。
输出：
最少需要安装的多少个喷水头；若没有符合要求的喷水头安装方案 ，则输出-1。
从线段的起点向终点安装喷水头，令f(X)表示：所安装喷水头的喷洒范围恰好覆盖直线上的区间[0 X]时，最少需要多少个喷水头
显然，X应满足下列条件
- X为偶数
- X所在位置不会出现奶牛，即X不属于任何一个(S,E)
- X>=2A
- 当X>2B时，存在Y属于[X-2B X-2A]且Y满足上述三个条件，使得 f(X)=f(Y)+1
递推计算f(X)
- f(X) = ∝ ： X 是奇数
- f(X) = ∝ ： X < 2A f(X) = ∝ ：X处可能有奶牛出没
- f(X)=1： 2A<=X<=2B 、且X位于任何奶牛的活动范围之外
- f(X)=1+min{f(Y): Y[X-2B X-2A]、Y位于任何奶牛的活动范围 之外}：X>2B,f(X)=1+min{f(Y): Y属于[X-2B X-2A]、Y位于任何奶牛的活动范围之 外}：X>2B
- 对每个X求f(X)，都要遍历区间[X-2B, X -2A]去寻找其中最小的 f(Y),则时间复杂度为：L * B = 1000000 * 1000，太慢。
- 快速找到[X-2B X-2A]中使得f(Y)最小的元素是问题求解速度的关键。
- 可以使用优先队列priority_queue! (multiset也可以，比 priority_queue慢一点）!
- 求F(X)时，若坐标属于[X-2B, X-2A]的二元组(i,F(i))都保存在一 个priority_queue中,并根据F(i)值排序，则队头的元素就能确保 是F(i)值最小的。
- 在求X点的F(x)时，必须确保队列中包含所有属于[X-2B,X-2A]的点。 而且，不允许出现坐标大于X-2A的点，因为这样的点对求F(X)无用， 如果这样的点出现在队头，因其对求后续点的F值有用，故不能抛弃之 ，于是算法就无法继续了。
- 队列中可以出现坐标小于X-2B 的点。这样的点若出现在队头，则直接将其抛弃。
- 求出X点的F值后，将(X-2A+2, F(X-2A+2))放入队列，为求F(X+2)作 准备
- 队列里只要存坐标为偶数的点即可。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int INFINITE = 1 << 31; //表示无解
const int MAXL = 1000010; //线段最大值，数值设大点是为了防止数据越界
const int MAXN = 1010; //奶牛数最大值
//状态：f(X)表示：所安装喷水头的喷洒范围恰好覆盖直线上的区间[0 X]时，最少需要多少个喷水头
int F[MAXL];
//cowThere[i]==1表示第i点有奶牛
int cowThere[MAXL];
int N, L, A, B;
struct Fx
{
int x;
int f;
Fx(int xx = 0, int ff = 0) : x(xx), f(ff)
{
}
bool operator <(const Fx& a) const
{
return f > a.f;
}
};
//Fx.f值升序排列
priority_queue<Fx> qFx;
int main()
{
// freopen("in.txt", "r", stdin);
cin >> N >> L >> A >> B;
memset(cowThere, 0, sizeof(cowThere));
for (int i = 0; i < N; i++) {
int s, e;
cin >> s >> e;
//奶牛活动区间：(s, e)，用cowThere记录奶牛区间临界点
++cowThere[s + 1];
--cowThere[e];
}
//输入数据为奶牛活动的半径，改为直径值，A、B都乘2后必为偶数，所以每次探索的右区间也为偶数
A <<= 1;
B <<= 1;
//计算cowThere真正的值
int inCows = 0; //当前点在多少头奶牛的活动范围之内
for (int i = 0; i <= L; i++) {
F[i] = INFINITE;
inCows += cowThere[i];
cowThere[i] = inCows > 0; //区间有进有出，类比()，用累加方式可能是否在区间内
}
//边界条件：f(X)=1： 2A<=X<=2B,且X位于任何奶牛的活动范围之外
for (int i = A; i <= B; i += 2) {
if (!cowThere[i]) {
F[i] = 1;
//下面求f(B+2)，不允许出现坐标大于X-2A的点
if (i <= B + 2 - A) {
qFx.push(Fx(i, 1));
}
}
}
//从f(B+2)一直计算到f(L), f(L)即为结果值
for (int i = B + 2; i <= L; i += 2) {
if (!cowThere[i]) {
Fx fx;
while (!qFx.empty()) {
fx = qFx.top();
//小于X-B的点抛弃，对f(X)而言，求f(X)=min(f(Y)) + 1, Y在[Y-B, Y-A]之间
if (fx.x < i - B) {
qFx.pop();
}
else {
break;
}
}
if (!qFx.empty()) {
//状态转移方程：f(X)=min(f(Y)) + 1
F[i] = fx.f + 1;
}
}
//下一个点是X=i+2，加入下一个点所需f(Y)，Y在[i+2-B, i+2-A]之间
if (F[i - A + 2] != INFINITE) {
qFx.push(Fx(i - A + 2, F[i - A + 2]));
}
}
if (F[L] == INFINITE) {
cout << -1 << endl;
}
else {
cout << F[L] << endl;
}
return 0;
}
2 8
1 2
6 7
3 6
3
方盒游戏
给定游戏开始时的状态，玩家可获得的最高积分是多少？
输入：第一行是一个整数t(1<=t<=15)，表示共有多少组测试数据。每组测试 数据包括两行
- 第一行是一个整数n(1<=n<=200),，表示共有多少个小块
- 第二行包括n个整数，表示每个小块的颜色。这些整数的取值范围是[1 n]
输出：对每组测试数据，分别输出该组测试数据的序号、以及玩家可以获得 的最高积分。
ClickBox(i,j,ex_len) 表示: 大块j的右边已经有一个长度为ex_len的大块(该大块可能是在合并过程中形成的，不妨就称其为ex_len)，且j的颜色和ex_len相 同，在此情况下将i到j以及ex_len都消除所能得到的最高分。
于是整个问题就是求：ClickBox(0,n-1,0)
求ClickBox(i,j,ex_len)时，有两种处理方法，取最优者 假设j和ex_len合并后的大块称作Q
- 将Q直接消除，这种做法能得到的最高分就是： ClickBox(i,j-1,0) + (len[j]+ex_len)2
- 期待Q以后能和左边的某个同色大块合并。需要枚举可能和Q 合并的大块。假设让大块k和Q合并，则此时能得到的最大 分数是： ClickBox(i,k,len[j]+ex_len) + ClickBox(k+1,j-1,0)
递归的终止条件：ClickBox(i,j,ex_len) 递归的终止条件： i == j
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define N 205
using namespace std;
int f[N][N][N],n,sum[N],a[N];
int main(){
// 定义一个二维数组f，用于存储每个子串的最大平方和
// 定义一个数组sum，用于存储每个元素出现的次数
// 定义一个数组a，用于存储输入的字符串
int t;cin>>t;int num=t;
// 定义一个变量t，用于存储输入的测试用例数
// 定义一个变量num，用于存储测试用例的编号
while(t--){
// 循环t次，每次处理一个测试用例
scanf("%d",&n);
// 输入字符串的长度
memset(sum,0,sizeof(sum));
// 将sum数组初始化为0
memset(f,0,sizeof(f));
// 将f数组初始化为0
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
// 输入字符串
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
// 遍历字符串，统计每个元素出现的次数
if(a[i]==a[j])sum[i]++;
}
}
// 遍历字符串，统计每个元素出现的次数
for(int i=n;i;--i){
for(int j=i;j<=n;++j){
for(int k=0;k<=sum[j];++k){
// 遍历每个子串，计算每个子串的最大平方和
f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(k+1)*(k+1));
// 如果当前子串的最后一个元素与前面的元素相等，则更新最大平方和
for(int p=i;p<j;++p){
if(a[p]==a[j]){
f[i][j][k]=max(f[i][j][k],f[i][p][k+1]+f[p+1][j-1][0]);
}
}
}
}
}
// 遍历每个子串，计算每个子串的最大平方和
printf("Case %d: %d\n",num-t,f[1][n][0]);
// 输出结果
}
return 0;
}
2
9
1 2 2 2 2 3 3 3 1
Case 1: 29
1
1
Case 2: 1