三角形牧场

P1284三角形牧场


题意

现在有n段木棍,全部使用组成三角形的三条边,使三角形的面积最大

分析

  • 首先看数据范围,边长最大为40*40/3,并且因为要使用所有的木棍,所以只要两条边确定就可以知道第三条边的确定长度。因此我们可以设状态f[i][j]表示三角形的两条边分别是i,j的情况是否成立

  • f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j],相当于01背包,就不解释了……

  • 定义初始状态f[0][0]=1f[0][0]=1

  • 三条边都知道了,如何求面积呢?这里我们需要用到海伦公式

    S=√p(p−a)(p−b)(p−c)S=p(p−a)(p−b)(p−c),p=12(a+b+c)p=12(a+b+c)

遇到的坑

好像没有什么

P1929 迷之阶梯

真的好坑,做了一下午……

题意

登上阶梯必须要按照它要求的方法, 否则就无法登上阶梯。它要求的方法有以下三个限制:

  1. 如果下一步阶梯的高度只比当前阶梯高 1,则可以直接登上。
  2. 除了第一步阶梯外,都可以从当前阶梯退到前一步阶梯。
  3. 当你连续退下 k 后,你可以一次跳上不超过当前阶梯高度 2^{k}2k的阶梯。比如说你现 在位于第 j 步阶梯,并且是从第 j+k 步阶梯退下来的,那么你可以跳到高度不超过当前阶 梯高度+2^{k}2k的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯,由于时间紧迫,我们需要用最少的移动次数登上迷之阶梯。 请你计算出最少的移动步数。

分析

  • 定义状态为f[i]表示到第i个阶梯的最小步数
  • 由2可以直接得出if(h[i]==h[i-1]+1) f[i]=f[i-1]+1

遇到的坑

  • if(f[n]>=0x3f3f3f3f) f[n]=-1;在状态转移的过程中有可能比初始值更大,所以是大于等于

动态规划习题2

P1970 花匠


分析

  • 第一次很容易就能想到转移方程:

    1
    2
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i]=f[i-1]+1;
    else if(a[i]<a[i+1] && a[i]<a[i-1]) f[i]=f[i-1]+1;

    但是这样做有一个很大的问题,无法确定最后一个状态的转移是否合法

    然后我就想找到最后一个状态是从哪里转移过来的,最后再额外判断一遍。虽然有点不像动态规划,只要用last1last2两个变量储存倒数第二个和第三个留下的点,但还是WA了2个点。

    原因好像是我丢掉了一些状态:我默认了只要这棵花能选就选,不满足无后效性

  • 动态规划

    正解:一维无法解决问题,那么就升一维。

    定义状态为f[i][j]表示第i个花处在上升或下降序列中能选的最多的花数

    状态转移方程为

    1
    2
    3
    4
    if(a[i]<a[i+1] && a[i]<a[i-1]) f[i][0]=f[i-1][1]+1;
    else f[i][0]=f[i-1][0];
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i][1]=f[i-1][0]+1;
    else f[i][1]=f[i-1][1];
  • 贪心

    为了方便我们设当前的花为A,下一盆花为B\

    • 第一盆花肯定要选,如果不选的话第二盆就成了第一盆,花的总数就会减少,一定不会比选第一盆花更优
    • 如果B比A还高,那么一定会选择B,因为落差的区间变大了,能够容纳的合法的花也变多了;同理,如果BA还小,那么一定会选择B
    • 通过以上两个判断不停地找波峰和波谷,记录答案就可以了

P1020 导弹拦截


非常恶心的一道题,我已经被搞晕了\

分析

  • 第一问就是求最长不上升子序列,想象有一个栈,如果当前数小于等于栈顶的数,则直接入栈;否则二分查找栈内第一个大于等于当前数的数并替换它,因为与当前数相等的数是有贡献的
  • 第二问就是求最长上升子序列,我不会证明,只能大概的胡诌,因为相当于我只关心子序列的长度,而只要有一个高度大于当前长度,就必须去新建一个序列,有点类似于木桶原理……

遇到的坑

  • 最长不下降子序列 等价于 倒序的最长不上升子序列
  • 最长下降子序列 等价于 倒序的最长上升子序列
  • lower_bound 二分查找第一个大于等于基准数的数(涵盖的范围更广)
  • upper_bound 二分查找第一个大于基准数的数

P1103 书本整理


很有感触的一道题\

分析

  • 可以抽象为:给定一串数列,首先对数列进行排序然后从数列中删除K个数使得整个数列每相邻两个数的差的绝对值的和最小,输出最小的和,即最小不整齐度。好拗口

  • f[i][j]表示长度为j的数列,数列最后一个的位置标号为j

  • 假设当前状态数列长度为j,现在以第i位为数列的最后一个,即最后一个肯定留下的最小不整齐度。因为这一位肯定要保留,所以状态肯定是从j-1转移过来的。其次我们就要枚举数列长度为j-1时,数列最后一个保留的数到底是多少,由此我们可以计算出应该增加的不整齐度

  • 转移方程:

    1
    f[i][j]=min(f[t][j-1]+abs(a[i]-a[t]),f[i][j]);//最后一个保留a[i],数列长度为j的最小不整洁度
  • 接下来考虑边界问题

    • j<=i 序列里的数肯定不会超过所有当前的数
    • t>=j-1 由上式同理可以得出,状态中的第一维度肯定大于等于第二维度
    • t<i 数列里的最后一个数肯定不可能达到现在及以后的数
    • j<=n-K 由题意可得……

    分析最清晰的一回

遇到的坑

  • f[n][n-k]并不是最终答案!!!只要状态里最后一个位置编号大于n-K,并且序列里有n-K个数,就有可能成为答案,所以我们要扫一遍找到最终答案
  • 赋初值!!! 因为我们状态转移选择的是最小值,最开始所有状态都是0,无论怎么转移都是0。所以我们把所有初值赋值为无穷大?显然不可行。我们可以每当需要转移该状态时,在确定该状态一定会被改变的前提下提前赋值为无穷大****
  • 真的都是很深很深的坑

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//与前文所使用的变量名有所不同
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=110;
struct ty
{
int h,w;
};
ty b[N];
int n,K,f[N][N];//是否保留

bool operator < (const ty &a,const ty &b)
{
return a.h<b.h;
}

int main()
{
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
scanf("%d%d",&b[i].h,&b[i].w);

K=n-K;
sort(b+1,b+n+1);

//第i个数保留j个的最小整齐度,序列的最后一个数序号为i
for(int i=1;i<=n;i++)
{
for(int j=1;j<=K&&j<=i;j++)
{
if(j==1) continue;
f[i][j]=0x3f3f3f3f;
for(int t=j-1;t<i;t++)
{
f[i][j]=min(f[t][j-1]+abs(b[i].w-b[t].w),f[i][j]);
}
// printf("f[%d][%d]=%d\n",i,j,f[i][j]);
}
}

int ans=0x3f3f3f3f;
for(int i=K;i<=n;i++)
ans=min(ans,f[i][K]);
printf("%d\n",ans);
return 0;
}

动态规划2-背包DP

动态规划2-背包DP

装箱问题

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入描述:一个整数v,表示箱子容量;一个整数n,表示有n个物品;接下来n个整数,分别表示这n 个物品的各自体积
输出描述:一个整数,表示箱子剩余空间。
样例输入: 24 6
​ 8 3 12 7 9 7
样例输出:0

状态:f[i][j]表示前i个物品能否装满j的体积

1
2
3
4
5
for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
f[i][j]=f[i-1][j] || f[i-1][j-v[i]];
for(int i=v;i>0;i++)
if(f[n][i]) printf("%d",v-i);

优化

  • 01滚动

    f[i][j]中每一次的状态转移只与上一行有关系,所以只需要一个2层的数组,可以用&1实现

  • 就地滚动

    每一次都会由左边的值转移到现在,所以每一次只要将循环从右往左就可以了


01背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

##方法1:动态规划
状态:还是一样,每一个背包只有选或者不选两种决策,这道题多了一个条件,相当于状态多了一个维度
转移方程f[i][j][k]=f[i-1][j][k]||f[i-1][j-v[i]][k-c[i]]
*i维度可以01滚动*

动态规划1

笔记

最优子结构:子结构最优,全局一定最优
无后效性:各个决策部分单独存在,不会相互影响

  1. 确定状态
    • 维度从低往高试
  2. 确定转移方程
    • 每一个状态的决策
    • 初始值
    • 边界问题
  3. 是否可以降低维度或其他优化

最大子串和


题意:给你一个有正有负的序列,求一个=子串(连续的一段),使其和最大!
样例输入: -5 6 -1 5 4 -7
样例输出: 14

状态:f[i]表示前i个数的最大子串和,每个状态只有两种决策:1. 与前面构成一个子串 2. 单独成为一个子串的开头
转移方程: f[i]=max(f[i−1]+a[i],a[i])f[i]=max(f[i−1]+a[i],a[i])

不相交的两个子串的最大和


给你一个有正有负的序列,求两个不重叠的子串,使其和最大!

方法一

两个不重叠的子串中间一定有一个分界点,我们可以枚举这个分界点,分别求出这个点左边的最大子串和以及右边的最大子串和

方法二

定义状态f[i][j]为前i个数组成了j个子串的最大值,当前状态下有两种选择,一种是与前面组成子串,一种是单独成为一个子串,但是需要枚举这个数前面的串的结尾在哪里
状态转移方程为f[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<if[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<i​
优化:可以用前缀和维护k维度,算出前k个数的最大和

最大子矩形


在一个矩阵中找到一个子矩阵,该子矩阵和最大!!输出最大和即可。

从暴力的角度考虑,这道题需要枚举矩形的两个顶点,也就是O(n^4)
我们可以只枚举两个顶点的行坐标,即找到这个矩形的高度所在的位置,然后把每一列的数之和求出来当做一个数,可以提前求出每一列前缀和,也就转化成了求最大子串和。

最长公共子序列


给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn},找出X和Y的一个最长公共子序列。

状态f[i][j]表示X的前i位与Y的前j位最长公共子序列的长度
转移方程

1
2
3
4
5
6
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(X[i]==Y[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}

回文词


回文词是一种对称的字符串——也就是说,一个回文词,从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。你的任务是写一个程序,求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”,在插入两个字符后可以变成一个回文词(“dAb3bAd”或“Adb3bdA”)。然而,插入两个以下的字符无法使它变成一个回文词。
给出一个字符串求出使其变为回文串需要插入的最少字符数。

思路:需要添加的字符的长度为原字符串的总长度减去现有的回文串长度,所以只要求出原字符串的回文串的长度就可以解决了
回文串的定义是正串与反串一样,那么正串与反串的最长公共子序列长度就是回文串的长度
*为什么不是最长公共子串长度?* 在添加字符的时候可以在任意位置插入,所以不必要求连续。所以如果只能从左右两边加入,那么就是最长公共子串长度

乘积最大


设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
如:有一个数字串:312, 当N=3,K=1时会有以下两种分法: 1) 312=36 2) 312=62
这时,符合题目要求的结果是:31*2=62

状态:f[i][j]表示前i位使用k个乘号的最大乘积
决策

  1. 这个数与前面的数组成更大的数,需要枚举这个数的起点
  2. 单独成为一个新数

在算乘积的时候可以先算出前缀‘乘’\
转移方程:

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
muti[i]*=muti[i-1]*a[i];
muti[0]=1;

for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
f[i][j]=f[i-1][j-1]*a[i];
for(int k=1;k<i;k++)
f[i][j]=f[k][j-1]*(muti[i]/muti[k-1]);
}