澳门娱乐6165会大概讲一下思路,后面慢慢补

作者:澳门娱乐

顺便开另外一篇放一些学过的各种dp

写这篇博文主要是为了归纳总结一下dp的有关问题(不定期更新,暑假应该会更的快一些)

dp总结: 

会大概讲一下思路,不会事无巨细地讲

开坑先放15道题,后面慢慢补

另一篇是平时做过的一些dp题,这篇博客里面提到的题都有题解放在那边:

目标50道题啦~~,目前50/50


 

这个玩意更新会有点慢,比较系统的学过一些dp的问题之后才会来写这个(可能要有人来催更才会写?)

1.合唱队形

题目链接

LIS模板题,这道题只要正着求一遍LIS,倒着求一遍LIS,然后求max即可,注意因为求了两次LIS,一定会有一个人是被计算了两次的,所以在求max的时候要记得-1

使用O(n2)做法即可

澳门娱乐6165 1澳门娱乐6165 2

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 110
ll n,a[N],f1[N],f2[N];
int main(){
    read(n);
    for(ll i=1;i<=n;i++)read(a[i]);
    for(ll i=1;i<=n;i++){
        f1[i]=1;
        for(ll j=1;j<i;j++){
            if(a[i]>a[j])f1[i]=max(f1[i],f1[j]+1);
        }
    }
    for(ll i=n;i;i--){
        f2[i]=1;
        for(ll j=i+1;j<=n;j++){
            if(a[i]>a[j])f2[i]=max(f2[i],f2[j]+1);
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)ans=max(ans,f1[i]+f2[i]-1);
    writeln(n-ans);
    return 0;
}

合唱队形

 


2.导弹拦截

题目链接

极其经典的dp题并且极其有趣而且对于初学者来说极其毒瘤,强烈推荐入手

这道题的输入就可以毒死一堆OI初学者了,代码里面会专门讲一下输入的方法

然后洛谷是有加强了一波数据的,需要$nlogn$解法才能过,这里两种解法都会说

一.最长上升子序列问题

大概意思是给一个序列,按从左到右的顺序选出尽可能多的数,组成一个上升子序列(子序列:对于一个序列,在其中删除1个或多个数,其他数的顺序不变)

随便来个序列:1 8 7 4 8 9

它的最长上升子序列是1 4 8 9(当然也可以是1 7 8 9)

对于这个问题,有O做法和O做法,这里两个做法都会讲到

1.O(n2)做法

对于第一问,直接跑一遍LIS就好,不过注意这里是最长下降子序列

对于第二问,可以用Dilworth定理,会在$nlogn$做法那里讲,这里讲一种贪心做法

因为问的是最少要多少个系统,那么我们肯定要让每个系统拦截尽可能多的导弹啊,所以对于目前已经开了的系统从小到大排序一遍,然后枚举,用目前可以拦截这颗导弹的且可拦截高度最低的系统来拦截(有点绕口,仔细想想)

要排序一遍,所以总复杂度其实是到了O(n2logn)的,不过原题这个复杂度也是可以过的

澳门娱乐6165 3澳门娱乐6165 4

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 100010
ll f[N],a[N],b[N];
bool vis[N];
int main(){
    ll n=0,m=0;
    while(scanf("%d",&a[++n])==1);n--;
    for(ll i=n;i;i--){
        f[i]=1;
        for(ll j=i+1;j<=n;j++){
            if(a[i]>=a[j]&&f[j]+1>f[i])f[i]=f[j]+1;
        }
        m=max(m,f[i]);
    }
    writeln(m);m=1;b[1]=a[1];
    for(ll i=2;i<=n;i++){
        ll pd=0;
        sort(b,b+m+1);
        for(ll j=1;j<=m;j++){
            if(a[i]<=b[j]){b[j]=a[i];pd=1;break;}
        }
        if(!pd)b[++m]=a[i];
    }
    writeln(m);
    return 0;
}

导弹拦截n^2做法

1.LIS的O做法

对于一个简单的LIS,你是怎么用肉眼判断的?一个一个往后找,然后数出最长的LIS,是不是?

n2做法就是用这种思路来做的,事实上这个做法就是一个优化后的暴力

设f[i]为以i为结尾的LIS的最大长度,则有

f[i]=max(f[i],f[j]+1)(a[i]>a[j])

代码如下:

for(int i=1;i<=n;i++){    f[i]=1;//这里不要忘记初始化,这是每个人都很容易忘记的地方    for(int j=1;j<i;j++){        if(a[i]>a[j])f[i]=max(f[i],f[j]+1);    }}

当然第二层循环也可以枚举j+1到n,都一样的,if里面的大于号改一下就好(这样的话就是f数组表示以ai为起点的最长上升子序列的)

这五行代码是LIS的基本模型,基本所有LIS的题都是对这五行代码添添改改搞出来的,所以在学习下面的东西之前需要务必确保自己完全搞懂这五行代码了再继续看

确保自己搞懂了之后可以先做一下例题中的合唱队形还有导弹拦截的n2做法

2.O(nlogn)做法

对于第一问,用LIS的$nlogn$做法跑一遍最长下降子序列就可以了

对于第二问,就要用Dilworth定理啦,不能用上面的贪心不然会TLE

讲一下Dilworth定理的大概意思:最少的下降序列个数就等于整个序列最长上升子序列的长度

不会证明,上面的链接有证明,虽然我看不懂

所以用nlogn做法跑一遍LIS就好了!

澳门娱乐6165 5澳门娱乐6165 6

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 100010
ll a[N],f[N],n,m;
int main(){
    while(scanf("%d",&a[++n])==1);
    n--;m=1;
    memset(f,127,sizeof(f));
    f[1]=a[1];
    for(ll i=2;i<=n;i++){
        if(f[m]>=a[i])f[++m]=a[i];
        else {
            ll l=0,r=m;
            while(l<r){
                ll mid=(l+r)>>1;
                if(f[mid]>=a[i])l=mid+1;
                else r=mid;
            }
            f[l]=a[i];
        }
    }
    writeln(m);m=1;
    memset(f,-1,sizeof(f));f[1]=a[1];
    for(ll i=2;i<=n;i++){
        if(f[m]<a[i])f[++m]=a[i];
        else {
            ll l=0,r=m;
            while(l<r){
                ll mid=(l+r)>>1;
                if(f[mid]>=a[i])r=mid;
                else l=mid+1;
            }
            f[l]=a[i];
        }
    }
    writeln(m);
    return 0;
}

导弹拦截nlogn做法

2.LIS的O做法

在学习LIS的nlogn做法之前,你需要两个前置姿势:知道什么是贪心,并且会打二分查找

想想LIS:在一个序列中选出尽可能多的数组成一个上升子序列。

让我们用用贪心的思想:

对于n2做法,我们是在求出以ai为结尾的LIS,以不断更新f数组的值的方式来维护LIS,而在这个过程中,f数组的值一定是最优的,而对于LIS来说,最优意味着什么?

对于最优的LIS,它的最后一位一定是尽可能小的,因为这样在后面更新的过程中,你才有更大的可能性让这个LIS变得更长

LIS的nlogn做法就是根据这种思想来做的,然后通过二分查找来使效率降到nlogn

相应的,f数组的含义也需要改一下:fi代表长度为i的LIS的最后一位数

在看代码之前请确保你理解了上面的贪心的思路

int m=1;//m是指LIS的长度,m=1是因为LIS的长度至少为1memset(f,127,sizeof;//初始化,这里的127表示的是无穷大f[1]=a[1];//初始化for(int i=2;i<=n;i++){    if(a[i]>f[m])f[++m]=a[i];//如果比当前的LIS的最后一位还大那这个LIS就可以变长了    else {//通过二分查找来更新f数组        int l=0,r=m;        while(l<r){            int mid=>>1;            if(a[i]>f[mid])r=mid;            else l=mid+1;        }        f[l]=a[i];//不要忘记更新    }}

想练一下LIS的nlogn做法的话就去试试洛谷的导弹拦截吧,可以去我的另一篇博客看题解qwq,链接在上面


 3.尼克的任务

题目链接

也不知道这算线性dp中的什么类型,看洛谷题解里面kkk说这是资源分配类的dp,姑且就这么认为吧

设$f[i]$为时间i尼克可以享有的最大空闲时间

很显然每个时间点尼克只会处于两种状态,要么在休息,要么在工作

所以可以得到两个转移方程:

对于这个时间点没有任务的情况:$f[i]=f[i-1]+1$

对于这个时间点有任务的情况:$f[i]=max(f[i],f[i+t])$ (t表示当前时间节点的任务的持续时间)

考虑顺推的方法,会发现对于i这个时间点,他的最大时间是和i+t有关的(t表示该任务的持续时间),而在顺推的情况下i+t这个时间点的最大时间是受到i的影响的

显然无法进行dp,推翻顺推解决的想法

于是就想想逆推,没有任务的情况只需要把上面那个转移方程的-1改成+1就好

对于这个时间点有任务的情况,可以直接枚举所有任务,对当前时间点开始做的任务,进行转移

澳门娱乐6165 7澳门娱乐6165 8

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 100100
ll n,k,f[N],sum[N];
struct node{ll p,t;}t[N];
bool cmp(node a,node b){return a.p>b.p;}
int main(){
    read(n);read(k);
    for(ll i=1;i<=k;i++){read(t[i].p);read(t[i].t);sum[t[i].p]++;}
    for(ll i=n;i;i--){
        if(sum[i]==0)f[i]=f[i+1]+1;
        else {
            for(ll j=1;j<=k;j++){
                if(t[j].p==i)f[i]=max(f[i],f[i+t[j].t]);
            }
        }
    }
    writeln(f[1]);
    return 0;
}

尼克的任务

二,最长公共子序列

公共子序列是指:一个同时是这两个序列的子序列的序列

有点绕口...反正就是那个意思

例如:

1 2 3 4 5

2 1 3 5 4

LCS的长度显然是3(1,3,4/2,3,4)

于是可以设f[i][j]表示第一个序列的前i位与第二个序列的前j位的LCS

答案就是f[len1][len2]

转移方程其实很好想的:

如果第一个序列的i位与第二个序列的j位相同,那么转移:f[i][j]=max(f[i-1][j],f[i][j-1])+1

如果不同那么考虑继承之前的最优答案:f[i][j]=max(f[i-1][j],f[i][j-1])

这里给例题中的 洛谷P1439[模板]最长公共子序列 的朴素LCS做法

#define ll int#define N 1010ll n,a[N],b[N],f[N][N];int main(){    scanf("%d",&n);    for(ll i=1;i<=n;i++)scanf("%d",&a[i]);    for(ll i=1;i<=n;i++)scanf("%d",&b[i]);    for(ll i=1;i<=n;i++){        for(ll j=1;j<=n;j++){            if(a[i]==b[j])f[i][j]=max(f[i-1][j],f[i][j-1])+1;            else f[i][j]=max(f[i-1][j],f[i][j-1]);        }    }    printf("%d",f[n][n]);    return 0;}

然后这道题的100%做法是很妙的,有兴趣的话可以去做一下(上面的做法只能50分)


 4.丝绸之路

题目链接

设$f[i][j]$为第j天在i城市的最小疲劳值

想一下转移方程就可以出来啦

$f[i][j]=min(f[i][j-1],f[i-1][j-1]+d[i]*c[j])$

记得初始化一下就好 $f[i][i]=f[i-1][i-1]+d[i]*c[i]$(不休息,直接从头走到尾)

代码

澳门娱乐6165 9澳门娱乐6165 10

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 1010
ll f[N][N],d[N],c[N],n,m;
//f[i][j]表示第j天在第i个城市的最小疲劳值 
int main(){
    read(n);read(m);
    for(ll i=1;i<=n;i++)read(d[i]);
    for(ll i=1;i<=m;i++)read(c[i]);
    for(ll i=1;i<=n;i++){
        f[i][i]=f[i-1][i-1]+c[i]*d[i];
        for(ll j=i+1;j<=m;j++){
            f[i][j]=min(f[i][j-1],f[i-1][j-1]+d[i]*c[j]);
        }
    }
    writeln(f[n][m]);
    return 0;
}

丝绸之路

三.区间dp

这个我应该会写多一点……

区间dp的定义:顾名思义,就是在对区间进行dp,一般是对小区间进行dp得出最优解,然后通过小区间的最优解得出一整个区间的最优解

大概是这样?反正也差不多,在没有题的情况下再怎么讲也很空泛,上面的定义随便看看就好,知道区间dp是个什么东西就行,具体看下面的例题来理解。

5.分队问题

题目链接

首先看到这道题第一想法应该是贪心

这个贪心写法应该也很容易写,排序一遍,然后直接选就可以了

信心满满地提交,会发现WA掉前面两个点

这个贪心想法其实有一个很明显的错误

来一组数据

4

2 3 3 3

贪心做法会输出2,但实际上应该输出1

所以这个贪心的想法是必须cut掉的,因为它没有考虑到分队时剩下来的人的a[i]对于队伍人数的限制

然而这个贪心做法在洛谷能拿80..

顺便说一下这是我校某次测评的题目啊,当时就写了这个贪心,然后挂的挺惨的

那么来想想dp做法

设f[i]表示前i个人能够分成的最大的队伍个数

从小到大排序一遍之后,显然可以发现,当第i个人可以加入这个队伍时,当且仅当 $i>=a[i]$

所以可以得到一个转移方程: f[i]=max(f[k])+1(0<i<=a[i])

但是这样对于百万级别的n是会超时的

考虑怎么去优化它

我们可以开一个数组来储存 f[1]$到$f[n]的最大值

则转移方程可以改成: f[i]=g[i-a[i]]+1

对于g数组的维护:g[i]=max(g[i-1],f[i])

这样就可以完成O(n)转移

澳门娱乐6165 11澳门娱乐6165 12

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 1000100
ll n,a[N],f[N],g[N];
int main(){
    read(n);
    for(ll i=1;i<=n;i++)read(a[i]);
    sort(a+1,a+n+1);
    for(ll i=1;i<=n;i++){
        if(i>=a[i])f[i]=g[i-a[i]]+1;
        g[i]=max(f[i],g[i-1]);
    }
    writeln(f[n]);
    return 0;
}

分队问题

1.矩阵链乘问题

这是紫书和算导都有的东西,不过我没有在OJ上面找到这道题...

首先在讲这道题之前我们要明确矩阵乘法的几个概念

1.两个矩阵能够相乘,当且仅当矩阵A的列数等于矩阵B的行数

2.设矩阵A的规模为n*p,矩阵B的规模为p*m,则这两个矩阵相乘的运算量为n*m*p

2.矩阵乘法满足结合律但不满足分配律

在明白矩阵乘法的概念之后,就可以来看这道题了

题意:给n个矩阵,全部都要乘起来,最后得到一个矩阵,你可以给他们加括号改变运算顺序,求最少的运算量,假设第i个矩阵Ai的规模是pi-1*pi

显然,加不加括号对这道题的运算量的影响是巨大的,举个例子,对于三个矩阵A,B,C,假设他们分别是2*3,3*4,4*5的,那么*C的运算量为64,A*的运算量为90,,这两种运算方式得出的最终的矩阵其实是一样的,但是运算量差别就很大了。

那么怎么解决这道题?

我们不妨用一般解dp题的思路来看看,把这一整个序列分成多个小的序列

设l为一个小序列的左端点,r为一个小序列的右端点,那么当这个小序列足够小,运算量显然为0(你没办法用它自己来乘它自己),这样我们就能得出初始化的情况了

然后假设我们现在正在求解某个子问题,这一次乘法是第k个乘号,那么我们一定已经算出A1*A2*···*Ak和Ak+1*Ak+2*···*An的最优结果,因此对于这一次相乘的结果它一定也是最优的(dp的最优子结构性质)

设我们正在求解的这个子问题的运算量为f[i][j],那么可得f[i][j]=min{f[i][k]+f[k+1][j]+pi-1*pj*pk}(k即上文我们提到的“最优的第k个乘号”)

那么有了转移方程后我们就可以来写这道题了吗?不,我们还需要注意到一个特殊的情况,如果采用递推求解的方式,因为需要满足dp的无后效性的性质,所以我们不能按照i/j的递增/递减顺序来进行运算,而是要以j->i递增的顺序来运算。

当然记忆化搜索就没有这个问题了,不过我不习惯打记忆化搜索,这一方面的话算导有讲到

总的时间复杂度为O

是的没有代码我懒得写,不过反正就是一个引入,应该不需要代码吧···理解一下思路

真的需要代码的话可以跟我讲下我去搞一下

6.低价购买

题目链接

第一问直接n2做法求LIS就好

对于第二问,其实是对第一问求出来的f数组进行进一步的dp

题目要求的数列是要去重的,但是放宽一下限制,先考虑不去重的情况

那么就可以得到转移方程:if(f[i]==f[j]+1&&a[i]<a[j])dp[i]+=dp[j]

考虑一下去重情况,如果以i为结尾的数列与以j为结尾的LIS大小相同且a[i]与a[j]是相同的,显然这两个LIS就是重复的

基于此,我们就可以得到去重的方法if(a[i]==a[j]&&f[i]==f[j])dp[i]=0

澳门娱乐6165 13澳门娱乐6165 14

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 5010
ll a[N],f[N],n,dp[N];
int main(){
    read(n);ll ans1=0;
    for(ll i=1;i<=n;i++)read(a[i]);
    for(ll i=1;i<=n;i++){
        f[i]=1;
        for(ll j=1;j<i;j++){
            if(a[i]<a[j])f[i]=max(f[i],f[j]+1);
        }
        ans1=max(f[i],ans1);
    }
    ll ans2=0;
    for(ll i=1;i<=n;i++){
        if(f[i]==1)dp[i]=1;
        for(ll j=1;j<i;j++){
            if(f[i]==f[j]+1&&a[i]<a[j])dp[i]+=dp[j];
            else if(f[i]==f[j]&&a[i]==a[j])dp[i]=0;
        }
    if(f[i]==ans1)ans2+=dp[i];
    }
    write(ans1);writeln(ans2);
    return 0;
}

低价购买

二.石子合并问题

题目链接

区间dp的例题,流传甚广的一道题,这里只给O做法,四边形不等式优化我不会啊>_<

与上一题相同,枚举断点划分子问题,通过子问题的最优解得出整个区间的最优解,区间dp的题都是这种套路

显然对于每个区间f[i][j],一定是由最优断点的结果转移过来的(不难证明:如果当前断点不是最优的,那么如果使用更优的断点得出的结果,也一定比当前断点更优)

于是设f[i][j]表示把i~j这个区间的石子合并为一堆石子的最小/最大花费

答案就是所有区间长度为n的区间的最大值/最小值

然后代码中的具体实现,我个人推荐的做法是枚举区间长度,左端点和断点,右端点可以通过左端点和区间长度的值算出来

还有就是对于石子的个数处理一下前缀和存在数组c中,这样在转移的时候就可以O得到i~j堆石子的合并花费

转移方程即为f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+c[j]-c[i-1])(对于最小值是min)

澳门娱乐6165 15澳门娱乐6165 16

#include <cstdio>#include <cstring>#define ll long long#define inf 1<<30#define il inline #define in1 read#define in2 in1#define in3 in2,in1#define in4 in2,in2il int max(int x,int y){return x>y?x:y;}il int min(int x,int y){return x<y?x:y;}il int abs(int x){return x>0?x:-x;}il void swap(int &x,int &y){int t=x;x=y;y=t;}il void readl(ll &x){    x=0;ll f=1;char c=getchar();    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    x*=f;}il void read(int &x){    x=0;int f=1;char c=getchar();    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    x*=f;}using namespace std;/*===================Header Template=====================*/#define N 210int n,f_min[N][N],f_max[N][N],a[N],c[N];int main(){    in1;    for(int i=1;i<=n;i++)in1,a[i+n]=a[i];    for(int i=1;i<=2*n;i++)c[i]=c[i-1]+a[i];    for(int len=2;len<=n;len++){        for(int i=1;i<=2*n;i++){            int j=i+len-1;f_min[i][j]=inf;            for(int k=i;k<j;k++){                f_min[i][j]=min(f_min[i][j],f_min[i][k]+f_min[k+1][j]+c[j]-c[i-1]);                f_max[i][j]=max(f_max[i][j],f_max[i][k]+f_max[k+1][j]+c[j]-c[i-1]);            }        }    }    int ans_max=0,ans_min=inf;    for(int i=1;i<=n;i++){        ans_max=max(ans_max,f_max[i][i+n-1]);        ans_min=min(ans_min,f_min[i][i+n-1]);    }    printf("%dn%dn",ans_min,ans_max);    return 0;}

石子合并


7.回文字串

题目链接

很巧妙的一道题啊...看到之后是极其懵逼的,完全不知道怎么写,于是悄咪咪地翻了一下学长的博客

get了一个很巧妙的解法:

回忆一下回文串的性质:正着读反着读都是一样的

那么我们可以把原数组倒过来,然后求出两个数组中已经构成"回文"的部分,这里可以使用LCS来求解

然后串的长度减掉LCS的长度就是答案啦

转移方程:

$if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1$

$f[i][j]=max(f[i-1][j],f[i][j-1])$

澳门娱乐6165 17澳门娱乐6165 18

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 1010
char s1[N],s2[N];
ll f[N][N],n;
int main(){
    scanf("%s",s1+1);n=strlen(s1+1);
    for(ll i=1;i<=n;i++)s2[n-i+1]=s1[i];
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    writeln(n-f[n][n]);
    return 0;
}

回文字串

四.最大子段和问题

挺简单的一类dp问题

最大子段和问题是这样的:

给你一个序列,正负不定,你需要求出$a[i]+a[i+1]+···+a[j-1]+a[j]$的最大值$(1<=i<=j<=n)$

分治和dp的经典题

这里只讲dp做法

我们设$f[i]$表示从1到i的最大子段和,那么可以很简单的推出转移方程

$f[i]=max(f[i-1]+a[i],a[i])$

也可以换一种写法

if(f[i-1]>0)f[i]=f[i-1]+a[i];

else f[i]=a[i];

初始化f[1]=a[1]


以上就是最基础的几个dp类型啦

 8.[模板]最长公共子序列

题目链接

洛谷的一道模板题,不过这道题其实只有50%的数据算是模板吧,100%的做法很巧妙

因为这道题的两个数列是1~n的全排列,也就是说,这两个数列是没有不同的数字的,只是排列方法不同而已

那么你想到了什么?离散化!

比如输入数据为:

5
3 2 1 4 5
1 2 3 4 5

那么将第一个数列排序,得到他们的大小关系:1-3,2-2,3-1,4-4,5-5

对第二个数列离散:1-3,2-2,3-1,4-4,5-5,也就是说第二个数列被我们搞成了这样:3 2 1 4 5

显然,离散后的第二个数列的LIS就是我们要求的解了

于是只需要在输入过程中把第二个数列离散成第一个数列的排序方式,然后对第二个数列求LIS就好了

求LIS要用$O(nlogn)$做法

澳门娱乐6165 19澳门娱乐6165 20

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 100010
ll n,a1[N],a2[N],f[N],map[N];
int main(){
    read(n);
    for(ll i=1;i<=n;i++){read(a1[i]);map[a1[i]]=i;}
    for(ll i=1;i<=n;i++){read(a2[i]);a2[i]=map[a2[i]];}
    memset(f,127,sizeof(f));
    f[0]=0;ll m=0;
    for(ll i=1;i<=n;i++){
        if(a2[i]>f[m])f[++m]=a2[i];
        else {
            ll l=0,r=m;
            while(l<r){
                ll mid=(l+r)>>1;
                if(f[mid]>=a2[i])r=mid;
                else l=mid+1;
            }
            f[l]=a2[i];
        }
    }
    writeln(m);
    return 0;
}

[模板]最长公共子序列

9.魔族密码

题目链接

不是很难的一道dp,排序一遍,然后再hash一下每个字符串

看是不是前缀只需要看hash值是不是相同的就好,如果相同就转移:$f[i]=max(f[i],f[j]+1)$

这里要排序是因为dp需要满足无后效性,排序之后可以保证第i个字符串之后的字符串一定不会是第i个字符串的前缀(以字符串长度为关键字进行排序)

效率$O(n2)$,因为这题的数据范围不大,如果大的话就最好开一下双hash/三hash/自然溢出hash

澳门娱乐6165 21澳门娱乐6165 22

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 2010
ll n,f[N],ans=0;
struct node{char ch[76];ll len;}a[N];
#define base 233
#define mod 19260817
#define ull unsigned long long
ull h[N][76];
bool cmp(node a,node b){return a.len<b.len;}
int main(){
    read(n);
    memset(h,0,sizeof(h));
    for(ll i=1;i<=n;i++){
        scanf("%s",a[i].ch+1);
        a[i].len=strlen(a[i].ch+1);
        f[i]=1;
    }
    sort(a+1,a+n+1,cmp);
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=a[i].len;j++)
            h[i][j]=(h[i][j-1]*base+(ull)(a[i].ch[j]))%mod;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<i;j++){
            if(a[i].ch[1]!=a[j].ch[1])continue;
            if(h[i][a[j].len]==h[j][a[j].len])f[i]=max(f[i],f[j]+1);
        }
        ans=max(ans,f[i]);
    }
    writeln(ans);
    return 0;
}

魔族密码

10.创意吃鱼法

 题目链接

这道题挺好玩的,在做这道题之前推荐先去写一下最大正方形这道题,写完后思路会清晰很多,下面也会放一下最大正方形的AC代码

对于这道题,初始化一下,设l表示i点开始往左的0的个数,r表示i点开始往上的0的个数

设$f[i][j]$为以(i,j)为右下角能吸到的最多的鱼

那么如果你写过最大正方形这道题,就可以很快的想出转移方程(其实没写过也能想出来):

f[i][j]=min(f[i-1][j-1],min(l[i-1][j],r[i][j-1]))+1(a[i][j]==1)

然后因为是一个矩形的对角线,而矩形是有两条对角线的,所以还要扫一遍

这个时候$f[i][j]$为以(i,j)为左下角能吸到的最多的鱼

注意l,r,f都要清零,还有因为是左下角,所以第二次dp是要倒推的

最后的答案就是$max(f[i][j])$

澳门娱乐6165 23澳门娱乐6165 24

#include <cstdio>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 2600
ll n,m,a[N][N],f[N][N],ans=0,l[N][N],r[N][N];
int main(){
    read(n);read(m);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            read(a[i][j]);
            if(!a[i][j])l[i][j]=l[i-1][j]+1,r[i][j]=r[i][j-1]+1;
            else f[i][j]=min(f[i-1][j-1],min(l[i-1][j],r[i][j-1]))+1;
            ans=max(ans,f[i][j]);
        }
    }
    memset(f,0,sizeof(f));
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    for(ll i=1;i<=n;i++){
        for(ll j=m;j;j--){
            if(!a[i][j])l[i][j]=l[i-1][j]+1,r[i][j]=r[i][j+1]+1;
            else f[i][j]=min(f[i-1][j+1],min(l[i-1][j],r[i][j+1]))+1;
            ans=max(ans,f[i][j]);
        }
    }
    writeln(ans);
    return 0;
}

创意吃鱼法

澳门娱乐6165 25澳门娱乐6165 26

#include <cstdio>
#include <cmath>
#include <cstring>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 110
ll a[N][N],f[N][N],n,mx=0,m;
int main(){
    read(n);read(m);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            read(a[i][j]);
            if(a[i][j]==1)f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
            mx=max(f[i][j],mx);
        }
    }
    writeln(mx);
}

最大正方形

 11.UVA10635 Prince and Princess

题目链接

这里先讲下,如果之后有放UVA的题的话都会挂洛谷的链接qwq,不然某些电脑进uva真的慢死(例如我校机房)...

题意:求两个序列的LCS,长度分别为p+1和q+1,极端情况下p,q<=62500,单个序列中的数都不相同

这题的题意其实也很迷... 有点难看出来是求LCS,而且LCS的解法是O(pq)对于可能高达62500的p,q是肯定TLE的,所以想想某些玄学解法

然后就会想起上面的第八题,是的,一模一样,还是离散化,把q序列离散成p序列的排列方式,对离散后的q序列搞一遍O(nlogn)的LIS就可以了

随便找找dp居然还找得到一样的题...

然后就是注意一下二分不要打挂,我二分初始化打挂WA了6次...

澳门娱乐6165 27澳门娱乐6165 28

#include <cstdio>
#include <cstring>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il int max(int x,int y){return x>y?x:y;}
il int min(int x,int y){return x<y?x:y;}
il int abs(int x){return x>0?x:-x;}
il void swap(int &x,int &y){int t=x;x=y;y=t;}
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 100010
int a[N],p[N],q[N],n,l1,l2,f[N];
int main(){
    int t;in1(t);
    for(int k=1;k<=t;k++){
        memset(f,127,sizeof(f));
        in3(n,l1,l2);
        for(int i=1;i<=l1+1;i++){int x;in1(x);p[x]=i;}
        for(int i=1;i<=l2+1;i++){int x;in1(x);q[i]=p[x];}
        int m=1;f[1]=q[1];
        for(int i=1;i<=l2+1;i++){
            if(q[i]==0)continue;
            if(q[i]>f[m])f[++m]=q[i];
            else {
                int l=1,r=m;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(f[mid]>q[i])r=mid;
                    else l=mid+1;
                }
                f[l]=q[i];
            }
        }
        printf("Case %d: %dn",k,m);
    }
    return 0;
}

UVA10635

12.木棍加工

题目链接

很水的一道dp,貌似贪心也可以水过去

因为有两个限制条件,所以先把这些木棍按其中一个关键字排序一下,这个关键字就对我们的结果没有什么影响了

在只有一个限制条件的情况下,其实就是求最小的最长下降子序列的个数,于是就想到了上面导弹拦截那道题(第二题)第二问用到的定理

Dilworth定理的大概意思:最少的下降序列个数就等于整个序列最长上升子序列的长度

于是找一遍最长上升子序列就好,因为n<=5000,直接用n2做法就好,如果再大一点就用$nlogn$做法,这里并不需要

澳门娱乐6165 29澳门娱乐6165 30

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il int max(int x,int y){return x>y?x:y;}
il int min(int x,int y){return x<y?x:y;}
il int abs(int x){return x>0?x:-x;}
il void swap(int &x,int &y){int t=x;x=y;y=t;}
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 5010
int n,f[N];
struct node{int w,l;}a[N];
bool cmp(node a,node b){
    if(a.w!=b.w)return a.w>b.w;
    else return a.l>b.l;
}
int main(){
    in1(n);int mx=0;
    for(int i=1;i<=n;i++)in2(a[i].l,a[i].w);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(a[i].l>a[j].l)f[i]=max(f[i],f[j]+1);
        }
        mx=max(f[i],mx);
    }
    printf("%dn",mx);
    return 0;
}

木棍加工

 13.[USACO08MAR]跨河River Crossing

题目链接

题目描述有点迷...注意看下面的样例解释啊,语文不好解释不来,就直接放题解了

不难的一道线性dp,设$f[i]$表示送前i只牛过河的最小时间花费

预处理一下一个c数组表示一次性送i只牛过河的花费

转移方程就不难得出了:$f[i]=min(f[i],f[j]+c[i-j])(i>j)$

记得初始化$f[i]=c[i]$,还有就是最后输出的时候要减掉m,因为最后一次过河之后john并没有再回去

澳门娱乐6165 31澳门娱乐6165 32

#include <cstdio>
#include <cstring>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il int max(int x,int y){return x>y?x:y;}
il int min(int x,int y){return x<y?x:y;}
il int abs(int x){return x>0?x:-x;}
il void swap(int &x,int &y){int t=x;x=y;y=t;}
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 3010
int a[N],c[N],n,m,f[N];
//fi送i头牛过河最小花费 
int main(){
    in2(n,m);
    for(int i=1;i<=n;i++)in1(a[i]);
    c[0]=2*m;
    for(int i=1;i<=n;i++)c[i]=c[i-1]+a[i];
    for(int i=1;i<=n;i++){
        f[i]=c[i];
        for(int j=1;j<i;j++){
            f[i]=min(f[i],f[j]+c[i-j]);
        }
    }
    printf("%dn",f[n]-m);
    return 0;
}

[USACO08MAR]跨河River Crossing

 14.UVA11400 Lighting System Design

题目链接

大概题意是,给你多组数据,对于每组数据,给你n种灯泡,每个灯泡有电压,电源费用,安装费用,需求量四个属性,可以用电压高的灯泡来代替电压低的灯泡以减少电源/安装费用的花费,求你的最低花费

洛谷的翻译其实还是有点迷,不过我讲的好像也有点迷...如果还是不懂题意可以去看紫书,这是里面的一道例题。

设f[i]表示前i种灯泡的最小价值

把它从小到大排序一下,再预处理一个c数组储存前i种灯泡的总需求量

那么$f[i]=min(f[i],f[j]+(c[i]-c[j])*a[i].c+a[i].k)$

那么答案就是$f[n]$了,还有就是记得初始化,把$f[i]$初始化为前i种电灯泡全用这种类型的灯泡所需的价格

澳门娱乐6165 33澳门娱乐6165 34

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il int max(int x,int y){return x>y?x:y;}
il int min(int x,int y){return x<y?x:y;}
il int abs(int x){return x>0?x:-x;}
il void swap(int &x,int &y){int t=x;x=y;y=t;}
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 1010
int n,f[N],c[N];
//前i种灯的最优价值 
struct node{int v,k,c,l;}a[N];
bool cmp(node a,node b){return a.v<b.v;}
int main(){
    while(scanf("%d",&n)==1&&n){
        for(int i=1;i<=n;i++){
            in4(a[i].v,a[i].k,a[i].c,a[i].l);
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++)c[i]=c[i-1]+a[i].l;
        for(int i=1;i<=n;i++){
            f[i]=a[i].k+a[i].c*c[i];
            for(int j=1;j<i;j++){
                f[i]=min(f[i],f[j]+(c[i]-c[j])*a[i].c+a[i].k);
            }
        }
        printf("%dn",f[n]);
    }
    return 0;
}

uva11400

15.出租车拼车

题目链接

设 $f[i][j] $表示 前 i 辆车载了 j 个oier的最优解。

$f[i][j]=min(f[i-1][j-x]+x*t[i]+d)  (1≤x≤min(z[i],j))$

$f[i][j]=f[i-1][j]  (x=0)$即如果没有人上车,就不需要付 d 元 

需要注意一下初始化,对于第0辆车,不管怎么载都没办法载(都没有这辆车,但是转移又要用到),所以就初始化$f[0][i]=inf$

那么答案就是 $f[k][n]$

澳门娱乐6165 35澳门娱乐6165 36

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a);in1(b)
#define in3(a,b,c) in2(a,b);in1(c)
#define in4(a,b,c,d) in2(a,b);in2(c,d)
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 500
int f[N][N],t[N],z[N];
//前i辆车载j个oier 
int n,k,d,s; 
int main(){
    in4(n,k,d,s);ll sum=0;
    for(ll i=1;i<=k;i++){in2(t[i],z[i]);sum+=z[i];}
    if(sum<n){printf("impossiblen");return 0;}
    for(ll i=1;i<=n;i++)f[0][i]=inf;
    for(ll i=1;i<=k;i++){
        for(ll j=1;j<=n;j++){
            f[i][j]=inf;
            for(ll k=0;k<=min(z[i],j);k++){
                if(k==0)f[i][j]=f[i-1][j];
                else f[i][j]=min(f[i][j],f[i-1][j-k]+t[i]*k+d);
            }
        }
    }
    printf("%dn",f[k][n]);
    return 0;
}

出租车拼车


15道题搞完啦,现在也已经暑假了,更新速度就会比较快啦

然后对于不同题库的题,如果洛谷有remotejudge我就直接挂洛谷的链接啦

弄个目标,50道题~

好像有点多...努力填啦


 16.最佳课题选择

题目链接

挺简单的一道dp,设$f[i][j]$表示用前i个课题完成j篇论文,那么答案就是$f[n][m]$

这道题的转移方程挺容易想的:$f[i][j]=min(f[i][j],f[i-1][j-k]+a[i]*k^b[i])$

初始化的话枚举到的状态一开始全都赋值inf就好,$f[0][i]$也赋值inf,但是不赋值貌似也没什么问题

快速幂打不打无所谓,记得开ll不然会爆

澳门娱乐6165 37澳门娱乐6165 38

#include <cstdio>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) readl(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il int max(int x,int y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il int abs(int x){return x>0?x:-x;}
il void swap(int &x,int &y){int t=x;x=y;y=t;}
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 500
ll n,m;
ll a[N],b[N],f[N][N];
//前i个课题拿来写j篇论文 
ll power(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1)ans*=base;
        base*=base;
        b>>=1;
    }
    return ans;
}
int main(){
    in2(n,m);
    for(ll i=1;i<=m;i++){
        in2(a[i],b[i]);
    }
    for(ll i=1;i<=n;i++)f[0][i]=inf;
    for(ll i=1;i<=m;i++){
        for(ll j=1;j<=n;j++){
            f[i][j]=inf;
            for(ll k=0;k<=j;k++){
                f[i][j]=min(f[i][j],f[i-1][j-k]+a[i]*power(k,b[i]));
            }
        }
    }
    printf("%lldn",f[m][n]);
    return 0;
}

最佳课题选择


暂时弃坑qwq,最近要刷noip..如果刷到dp题就继续补上来qwq


 17.[USACO06FEB]澳门娱乐6165,奶牛零食Treats for the Cows

题目链接

挺常规的一个区间dp,不过就是不用枚举分割点了,直接枚举长度和左端点就好了

初始化$f[i][i]=a[i]*n$如果只有这一个当然是放到最后一天卖赚最多

然后转移的时候,从更小的那个区间更新就可以了,天数其实就是$n-len+1$,因为我们的区间其实是剩下的区间,也就是已经取了$n-len+1$天

方程:$f[l][r]=max(f[l][r-1]+a[r]*(n-len+1),f[l+1][r]+a[l]*(n-len+1))$

澳门娱乐6165 39澳门娱乐6165 40

#include <cstdio>
using namespace std;
int n,a[2010];
int f[2010][2010];
int max(int x,int y){return x>y?x:y;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)f[i][i]=a[i]*n;
    for(int len=2;len<=n;len++){
        for(int l=1;l<=n;l++){
            int r=len+l-1;
            if(r>n)continue;
            f[l][r]=max(f[l][r-1]+a[r]*(n-len+1),f[l+1][r]+a[l]*(n-len+1));
        }
    }
    printf("%d",f[1][n]);
    return 0;
}

奶牛零食


 18.能量项链

题目链接

和矩阵链乘问题有点像,简单区间dp,记得断链成环就行

方程f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1])

澳门娱乐6165 41澳门娱乐6165 42

#include <cstdio>
using namespace std;
int n,f[210][210],a[210],mx=0;
int max(int x,int y){return x>y?x:y;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=2*n;i>=1;i--)
        for(int j=i+1;j<=2*n;j++)
            for(int k=i;k<j;k++)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
    for(int i=1;i<=2*n;i++){
        mx=max(f[i][i+n-1],mx);
    }
    printf("%dn",mx);
    return 0;
}

能量项链


 19.跳房子

这道题我专门写一个题解..noip2017普及组的T4

传送门


 20.摆花

简单dp

设$f[i][j]$表示前i种花一共用了j盆时的最优解,那么很显然$f[i][j]=sum(f[i-1][j-a[i]...j])$

答案就是$f[n][m]$

澳门娱乐6165 43澳门娱乐6165 44

#include <cstdio>
#define mod 1000007
using namespace std;
//f[i,j]表示第i种花一共选了j盆 
int f[1000][1000],a[1000],n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=a[i];k++){
                if(j-k>=0)f[i][j]=(f[i][j]+f[i-1][j-k])%mod; 
            }
        }
    }
    printf("%dn",f[n][m]%mod);
    return 0;
} 

摆花


 21.HDU5115 

题目链接

题目大意是:有n头狼,初始攻击力为$ai$,然后可以只要活着就可以给左右两边的队友加buff,加$bi$点攻击力,也就是说你杀死一头狼一共会受到$a[i]+b[i-1]+b[i+1]$点伤害,假设第i-1头狼和第i+1头狼还活着的话,现在要最小化杀死所有狼收到的伤害

设$f[l][r]$表示杀死l到r头狼受到的最小伤害,那么很容易得到转移方程

$f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+a[k]+b[l-1]+b[r+1])$(设k为我们在杀死l到r头狼时最后杀死的那头狼)

澳门娱乐6165 45澳门娱乐6165 46

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define N 500
#define inf (1<<30)
ll f[N][N];
ll n,a[N],b[N];
int main(){
    int t,kase=0;scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i<=j)f[i][j]=inf;
                else f[i][j]=0;
            }
        }
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%lld",&b[i]);
        for(int i=1;i<=n;i++)
            f[i][i]=a[i]+b[i-1]+b[i+1];
        for(int len=1;len<=n;len++){
            for(int l=1;l+len<=n;l++){
                int r=l+len;
                for(int k=l;k<=r;k++){
                    f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+a[k]+b[l-1]+b[r+1]);
                }
            }
        }
        printf("Case #%d: %lldn",++kase,f[1][n]);
    }
    return 0;
} 

HDU5115


 22.[USACO13NOV]POGO的牛Pogo-Cow

题目链接

这道题n^3的dp很好想...

设$f[i][j]$表示最后从i跳到j的最优解

那么显然$f[i][j]=max(f[i][j],f[k][j]+a[i].val)$

但是只能81...(不过开O2就能AC了)

考虑优化

我们可以改一下设的方程 $f[i][j]$表示最后从j跳到i的最优解

然后可以发现一个神奇的地方,k是我们要枚举的转移点,但是k是随着j的递增而递增的(当i不变的情况下,j增大k也会增大),所以就可以开一个单调队列来优化一下了

所以就成功优化到$O(N^2)$了

澳门娱乐6165 47澳门娱乐6165 48

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {int val,x;}a[2000];
bool cmp(node a,node b){
    return a.x<b.x;
}
int f[2000][2000]; 
//f[i,j]表示最后跳的两个点是i和j 
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].val);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            f[i][j]=a[i].val+a[j].val;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i-1;j;j--){
            for(int k=j-1;k;k--){
                if(a[j].x-a[k].x>a[i].x-a[j].x)continue;
                f[j][i]=max(f[j][i],f[k][j]+a[i].val);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans=max(f[i][j],ans);
        }
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            f[i][j]=a[i].val+a[j].val;
        }
    }
    for(int i=n;i;i--){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(a[k].x-a[j].x>a[j].x-a[i].x)continue;
                f[i][j]=max(f[i][j],f[j][k]+a[i].val);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans=max(f[i][j],ans);
        }
    }
    printf("%dn",ans);
    return 0;
} 

n^3

澳门娱乐6165 49澳门娱乐6165 50

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {int val,x;}a[2000];
bool cmp(node a,node b){
    return a.x<b.x;
}
int f[2000][2000]; 
//f[i,j]最后从j点跳到i点 
int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].val);
    }
    sort(a+1,a+n+1,cmp);
    for(int j=1;j<=n;j++){
        int k=j-1,val=f[j][0]+a[j].val;
        for(int i=j+1;i<=n;i++){
            while(k&&a[i].x-a[j].x>=a[j].x-a[k].x)
                val=max(val,a[j].val+f[j][k]),k--;
            f[i][j]=max(f[i][j],val);
            ans=max(ans,val+a[i].val);
        }
    } 
    for(int j=n;j;j--){
        int k=j+1,val=f[j][n+1]+a[j].val;
        for(int i=j-1;i;i--){
            while(k<=n&&a[j].x-a[i].x>=a[k].x-a[j].x)
                val=max(val,f[j][k]+a[j].val),k++;
            f[i][j]=max(f[i][j],val);
            ans=max(ans,val+a[i].val);
        }
    }
    printf("%dn",ans);
    return 0;
} 

n^2


 23.乌龟棋

啊挺简单的一道dp

设$f[a][b][c][d]$表示用了a张第一种牌b张第二种牌c张第三种牌d张第四种牌就行了

不过是因为题目中保证所有卡片用完正好到达终点才可以这么写

所以知道abcd就可以知道现在在哪个地方

就直接dp下去就行了

答案就是$f[suma][sumb][sumc][sumd]$

澳门娱乐6165 51澳门娱乐6165 52

#include <cstdio>
using namespace std;
int f[40][40][40][40],num[500],p[500];
inline int max(int x,int y){return (x)>(y)?(x):(y);}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]);
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        p[x]++;
    }
    f[0][0][0][0]=num[1];
    for(int a=0;a<=p[1];a++){
        for(int b=0;b<=p[2];b++){
            for(int c=0;c<=p[3];c++){
                for(int d=0;d<=p[4];d++){
                    int to=a+b*2+c*3+d*4+1;
                    if(a)f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+num[to]);
                    if(b)f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+num[to]);
                    if(c)f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+num[to]);
                    if(d)f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+num[to]);
                }
            }
        }
    }
    printf("%dn",f[p[1]][p[2]][p[3]][p[4]]);
    return 0;
} 

乌龟棋


 24.[USACO08JAN]跑步Running

题目链接

设$f[i][j]$表示第i分钟的疲劳度为j时的最优解

分类讨论一下各种情况,当现在的疲劳度为0的时候,很显然,就只有现在在休息,前一分钟也在休息的情况,所以对于j=0的情况这么转移就行

$f[i][j]=max(f[i][j],f[i-1][j])$

对于疲劳度不为0的情况,如果选择休息,因为只能休息到疲劳度为0,所以要这么转移

$f[i+j][0]=max(f[i][j],f[i+j][0])$

对于疲劳度不为0且要继续跑步的情况:

$f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+d[i+1])$

答案就是$f[n][0]$

澳门娱乐6165 53澳门娱乐6165 54

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,d[100000];
int f[10505][505];
//f[i,j]表示第i分钟的疲劳度为j的最优解 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
    }
    f[1][1]=d[1];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=min(m,i);j++){
            if(j==0){
                f[i][j]=max(f[i-1][0],f[i][j]);
            }else {
                f[i+j][0]=max(f[i+j][0],f[i][j]);//选择休息
            }
            f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+d[i+1]);//选择跑步
        }
    }
    printf("%dn",f[n][0]);
    return 0;
}

跑步


25.过河

题目链接

首先状态转移方程是不难推的...

$f[i]=min(f[i-j]+flag[i])$

但是这样子数组下标是最大可以到$10^9$,数组开不下

于是考虑一下压缩路径,这里介绍两种方法:

1.2520压缩,因为$gcd(1,10)=2520$,所以无论s,t是多少都一定可以跳到2520,所以两个石头间的距离大于2520就可以直接压掉2520的距离了

2.90压缩,这是一个利用$exgcd$推导出来的压缩方法,下面给一个证明的链接,这里就不证明了(太长),直接说结论:当两个石头的距离大于$t*(t-1)$那么就能压缩,而$t*(t-1)$的最大值是90

证明链接

压缩完后就可以直接上dp了!

但是以上压缩方法对于$s==t$的情况并不适用,需要特判

澳门娱乐6165 55澳门娱乐6165 56

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int l,m,s,t;
int f[50000],a[50000],flag[50000];
int main(){
    scanf("%d%d%d%d",&l,&s,&t,&m);
    if(s==t){
        int x,ans=0;
        for(int i=1;i<=m;i++){
            scanf("%d",&x);
            if(!(x%s))ans++;
        }
        printf("%dn",ans);
        return 0;
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    int cnt=0;a[0]=0;
    sort(a+1,a+m+1);
    a[m+1]=min(l-a[m],100);
    for(int i=1;i<=m;i++){
        f[i]=min(a[i]-a[i-1],90);
        cnt+=f[i];
        flag[cnt]=1;
    }
    cnt+=a[m+1];
    memset(f,127,sizeof(f));
    f[0]=0;
    for(int i=1;i<=cnt+9;i++){
        for(int j=s;j<=t;j++){
            if(i-s>=0){
                f[i]=min(f[i],f[i-j]+flag[i]);
            }
        }
    }
    int ans=1<<30;
    for(int i=cnt;i<=cnt+9;i++){
        ans=min(ans,f[i]);
    }
    printf("%dn",ans);
    return 0;
} 

过河


 26.[USACO07FEB]牛的词汇The Cow Lexicon

题目链接

啊,这道题的转移方式很神奇,看题解++

设$f[i]$表示从i开始往后要删多少个

那么对于A串的每个位置暴力匹配所有的B串,打个check就行了,设我们一共要删掉tot个单词,那么方程:

$f[i]=min(f[i],f[i+len[j]+tot]+tot)$

澳门娱乐6165 57澳门娱乐6165 58

#include <bits/stdc++.h>
using namespace std;
int f[1000],l[1000];
int w,L;
char a[1000],b[500][50];
int check(int i,int id){
    int tot=0;
    for(int j=1;i<=L;i++){
        if(a[i]==b[id][j])j++;
        else tot++;
        if(j==l[id]+1)return tot;
    }
    return -1;
}
int main(){
    scanf("%d%d",&w,&L);
    scanf("%s",a+1);
    for(int i=1;i<=w;i++){
        scanf("%s",b[i]+1);
        l[i]=strlen(b[i]+1);
    }
    for(int i=L;i;i--){
        f[i]=f[i+1]+1;
        for(int j=1;j<=w;j++){
            if(a[i]==b[j][1]){
                int pd=check(i,j);
                if(pd!=-1){
                    f[i]=min(f[i],f[i+l[j]+pd]+pd);
                }
            }
        }
    }
    printf("%dn",f[1]);
    return 0;
} 

牛的词汇


 27.[USACO07MAR]牛交通Cow Traffic

题目链接

又是一道神奇的dp....DAG上的dp

由乘法原理可得,一条路经过的次数等于左右两个点经过的次数相乘

于是从入度为0的点开始dp一遍,从n开始dp一遍,第二次记得反着建图

然后因为是在图上dp,所以可以采用搜索的方法来实现dp的转移

澳门娱乐6165 59澳门娱乐6165 60

#include <bits/stdc++.h>
#define N 100010
using namespace std;
struct edge {
    int to,nxt,v;
}e[N];
int head[N],cnt,n,m;
int in[N],q[N*10];
int x[N],y[N];
void ins(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int dp[N],f[N];
void dfs(int x){
    if(!head[x]){f[x]=1;return;}
    for(int i=head[x];i;i=e[i].nxt){
        if(!f[e[i].to])dfs(e[i].to);
        f[x]+=f[e[i].to];
    }
}
void dfs1(int x){
    if(!head[x]){dp[x]=1;return;}
    for(int i=head[x];i;i=e[i].nxt){
        if(!dp[e[i].to])dfs1(e[i].to);
        dp[x]+=dp[e[i].to];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u>v)swap(u,v);
        ins(u,v);
        x[i]=u;y[i]=v;
        in[v]++;
    }
    for(int i=1;i<=n;i++){
        if(!in[i])dfs1(i);
    }
    memset(head,0,sizeof(head));
    cnt=0;
    for(int i=1;i<=m;i++){
        ins(y[i],x[i]);
    }
    dfs(n);
    int ans=0;
    for(int i=1;i<=m;i++){
        ans=max(ans,f[x[i]]*dp[y[i]]);
    }
    printf("%dn",ans);
    return 0;
} 

牛的交通


28.[USACO07NOV]挤奶的时间Milking Time

题目链接

设$f[i]$表示做到第i件事时可以获得的最大收益

只要按右端点排序就能转移了

转移方程$f[i]=max(f[i],f[j]+a[i])$

也可以跑spfa最长路,x向y+r连边就行

澳门娱乐6165 61澳门娱乐6165 62

#include <bits/stdc++.h>
using namespace std;
int n,m,t;
struct node {
    int l,r,val;
}a[10000];
int f[1000000];
bool cmp(node a,node b){
    return a.r<b.r;
}
int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
    }
    int ans=0;
    sort(a+1,a+m+1,cmp);
    a[0].r=-1000000;
    for(int i=1;i<=m;i++){
        for(int j=0;j<i;j++){
            if(a[i].l-a[j].r>=t)f[i]=max(f[i],f[j]+a[i].val);
        }
        ans=max(ans,f[i]);
    }
    printf("%dn",ans);
} 

挤奶时间

 


29.装箱问题

题目链接

这个普及T4假的吧....就是01背包模板题,把体积顺便当做价值做一下01背包就可以了

澳门娱乐6165 63澳门娱乐6165 64

#include <bits/stdc++.h>
using namespace std;
int v,a[500],n,f[25500];
int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i];j--){
            f[j]=max(f[j],f[j-a[i]]+a[i]);
        }
    }
    int ans=0;
    printf("%dn",v-f[v]);
} 

装箱问题


30.[HNOI2004]打鼹鼠

题目链接

用类似LIS的做法...如果曼哈顿距离大于时间差那就转移...$O(N^2)$能过...

这也是个假的省选吧...

澳门娱乐6165 65澳门娱乐6165 66

#include <bits/stdc++.h>
using namespace std;
#define N 10010
int n,m,x[N],y[N],t[N];
int f[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)f[i]=1;
    int ans=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
        for(int j=1;j<i;j++){
            if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])
                f[i]=max(f[i],f[j]+1);
        }
        ans=max(ans,f[i]);
    }
    printf("%dn",ans);
}

[HNOI2004]打鼹鼠


31.道路游戏

NOIP2009T4,专门写了一篇博客来总结一下

传送门


32.[CQOI2007]涂色

专门写了一篇,虽然不难...

题解传送门


 33.[BeijingWc2008]雷涛的小猫

简单dp,优化一下就能过

WC居然有这种简单题?!

不过既然是WC题那肯定要再开一篇博客的啦(逃

传送门


 34.教主的花园

题目链接

好麻烦的一个dp...

我一开始想到的做法是设$f[i][j][k]$表示第i个位置种了第j种树,上一个位置种的是比它大还是比它小:1小2大 

然后码出来后交上去70...

翻了翻题解发现一堆和我遭遇一样的人...会70是因为这是个环,要考虑第一个和第n个

所以多加一维表示第一个地方放的哪种树

转移方程不放了直接看代码吧,一大堆...

澳门娱乐6165 67澳门娱乐6165 68

#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n,a[N][5];
int f[N][5][5][5];
//第i个位置种了第j种树,上一个位置种的是比它大还是比它小:1小2大 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i][1],&a[i][2],&a[i][3]);
    f[1][1][2][1]=a[1][1];
    f[1][2][2][2]=f[1][2][1][2]=a[1][2];
    f[1][3][1][3]=a[1][3];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=3;j++){
            f[i][1][2][j]=max(f[i-1][2][1][j],f[i-1][3][1][j])+a[i][1];
            f[i][2][1][j]=f[i-1][1][2][j]+a[i][2];
            f[i][2][2][j]=f[i-1][3][1][j]+a[i][2];
            f[i][3][1][j]=max(f[i-1][2][2][j],f[i-1][1][2][j])+a[i][3];
        }
    }
    int ans=0;
    ans=max(f[n][1][2][2],f[n][1][2][3]);
    ans=max(ans,max(f[n][2][2][3],f[n][2][1][1]));
    ans=max(ans,max(f[n][3][1][2],f[n][3][1][1]));
    printf("%dn",ans);
    return 0;
}

View Code


 35.烹调方案

题目链接

挺有意思的一个01背包

开始直接写了一个裸01背包30分

想了好久悄咪咪地翻了一下题解发现因为有$b[i]$这个属性所以先后选的顺序是有影响的

瞬间懂了

自己推一下就没什么问题了

这里放一下我的推导过程

$a[i]-b[i]*(t+c[i])+a[j]-b[j]*(t+c[i]+c[j])$//i先做
$a[j]-b[j]*(t+c[j])+a[i]-b[i]*(t+c[i]+c[j])$//j先做

$a[i]-b[i]*(t+c[i])+a[j]-b[j]*(t+c[i]+c[j])>a[j]-b[j]*(t+c[j])+a[i]-b[i]*(t+c[i]+c[j])$

$-b[i]*(t+c[i])-b[j]*(t+c[i]+c[j])>-b[j]*(t+c[j])-b[i]*(t+c[i]+c[j])$

$-b[i]*t-b[i]*c[i]-b[j]*t-b[j]*c[i]-b[j]*c[j]>-b[j]*t-b[j]*c[j]-b[i]*t-b[i]*c[i]-b[i]*c[j]$

$-b[j]*c[i]>-b[i]*c[j]$

所以最后按$-b[j]*c[i]>-b[i]*c[j]$的规则进行排序就行了

然后注意要开longlong,不然第十四个点排序的时候会爆掉...

澳门娱乐6165 69澳门娱乐6165 70

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,t;
struct node {
    ll a,b,c;
}a[100];
ll f[100000];
bool cmp(node i,node j){
    return -j.b*i.c>-i.b*j.c;
}
int main(){
    long long ans=0;
    scanf("%lld%lld",&t,&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].a);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].b);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].c);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=t;j>=a[i].c;j--){
            f[j]=max(f[j],f[j-a[i].c]+a[i].a-a[i].b*j);
            ans=max(ans,f[j]);
        }
    }
    printf("%lldn",ans);
    return 0;
}

烹调方案


 36.经营与开发

题目链接

有点思维难度...

正推有后效性所以倒推

转移的话呢,如果是资源型,那就把之前的结果改一下变成$f[i+1]*(1-0.01k)$就可以转移了,维修型的同理

澳门娱乐6165 71澳门娱乐6165 72

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
int n,k,c,w;
double f[N];
int type[N],a[N];
int main(){
    scanf("%d%d%d%d",&n,&k,&c,&w);
    for(int i=1;i<=n;i++)scanf("%d%d",&type[i],&a[i]);
    for(int i=n;i;i--){
        if(type[i]==1)f[i]=max(f[i+1],a[i]+f[i+1]*(1-0.01*k));
        else f[i]=max(f[i+1],f[i+1]*(1+0.01*c)-a[i]);
    }
    printf("%.2lfn",f[1]*w);
}

经营与开发


 37.货币系统

题目链接

简单题,裸的完全背包求方案数,初始化$dp[0]=1$

澳门娱乐6165 73澳门娱乐6165 74

#include <bits/stdc++.h>
using namespace std;
int n,m,a[50];
long long dp[10010];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=m;j++){
            dp[j]+=dp[j-a[i]];
        }
    }
    printf("%lldn",dp[m]);
}

货币系统


 38.[HAOI2012]音量调节

题目链接

比较神奇的背包...

一开始没有反应过来...

其实就是把能够到达的音量标记一下就可以了,初始化$f[0][begin]=1$

澳门娱乐6165 75澳门娱乐6165 76

#include <bits/stdc++.h>
using namespace std;
int n,beginl,Max,c[2000];
bool f[2100][2010];
int main(){
    scanf("%d%d%d",&n,&beginl,&Max);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
    }
    f[0][beginl]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=Max;j++){
            if(f[i-1][j])f[i][j+c[i]]=1;
            if(f[i-1][j]&&j-c[i]>=0)f[i][j-c[i]]=1;
        }
    }
    int ans=-1;
    for(int i=Max;i;i--){
        if(ans!=-1)break;
        if(f[n][i])ans=i;
    }
    printf("%dn",ans);
    return 0;
} 

音量调节


 39.机器分配

题目链接

简单dp...挺套路的一道题,虽然输出路径想了很久...

设$f[i,j]$表示前i个公司分配了j台机器

那么$f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k])$

注意k要从0枚举到j,因为这家公司可以一个都不取也可以全部都取...

输出的时候递归输出,枚举这一家人选了多少个,然后匹配一下$a[x][i]+f[x-1][y-i]==f[x][y]$

具体细节看代码吧

澳门娱乐6165 77澳门娱乐6165 78

#include <bits/stdc++.h>
using namespace std;
int n,m;
int f[100][100];
//f[i,j]表示前i个公司分配了j台机器 
int a[100][100];
void print(int x,int y){
    for(int i=y;i>=0;i--){
        if(a[x][i]+f[x-1][y-i]==f[x][y]){
            print(x-1,y-i);
            printf("%d %dn",x,i);
            break;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    }
    f[1][1]=a[1][1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<=j;k++){
                f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k]);
            }
        }
    }
    printf("%dn",f[n][m]);
    print(n,m);
    return 0;
} 

机器分配


 40.花店橱窗布置

题目链接

和上一题有点类似,也是一道套路题...

但是这种老题怎么总是喜欢输出路径啊....每次都琢磨好久才知道怎么输出...

就设$f[i,j]$表示第i个花瓶放第j种花的最优解

然后转移就是$f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[j][i])$

输出路径递归输出就行

澳门娱乐6165 79澳门娱乐6165 80

#include <bits/stdc++.h>
using namespace std;
int n,m;
int f[110][110];
#define inf 0x3f3f3f3f
//f[i,j]表示第i个花瓶放第j种花的最优解 
int a[110][110];
void print(int x,int val){
    if(!x)return;
    int i=x;
    while(f[i][x]!=val)i++;
    print(x-1,val-a[x][i]);
    printf("%d ",i); 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            f[j][i]=-inf;
        }
    }
    for(int i=1;i<=m;i++)f[0][i]=-inf;
    f[0][0]=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=min(n,i);j++){
            f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[j][i]);
        }
    } 
    printf("%dn",f[m][n]);
    print(n,f[m][n]);
    return 0;
} 

花店橱窗布置

不过这居然是IOI题?IOI题!写完才发现...虽然是1999年的...


 41.看球泡妹子

题目链接

不会说我是被标题吸引进去的

点进去后发现这题有点毒瘤,然后以顽强的毅力写掉了

我一开始想到的思路是:$f[i][j]$表示小红精彩度为i时看了j场比赛的最优解

然后就可以用类似01背包的方法,多加一维来写这题

但是写炸了...想了好久想不出来,然后翻了一下题解,发现没有相同思路的...

所以偷偷借鉴了一下题解的思路

$f[i][j][k]$表示前i场比赛一共看了j场,精彩度为k的最优解 

转移挺简单的:

$f[i][j][k]=max(f[i-1][j][k],f[i][j][k])$

$f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-w[i]]+v[i])$

我预处理了一下$wi$和$vi$不预处理直接算也行

澳门娱乐6165 81澳门娱乐6165 82

#include <bits/stdc++.h>
using namespace std;
int n,m,k,c;
int f[110][110][2020];
//f[i][j][k]表示前i场比赛一共看了j场,精彩度为k的最优解 
int a[1000],b[1000],w[1000],v[1000];
int main(){
    int sum=0;
    scanf("%d%d%d%d",&n,&m,&k,&c);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        w[i]=b[x]+b[y];
        v[i]=a[x]*a[y];
        sum+=w[i];
    }
    int ans=0;
    for(int j=1;j<=k;j++){
        for(int i=1;i<=m;i++){
            for(int k=sum;k>=0;k--){
                f[i][j][k]=max(f[i-1][j][k],f[i][j][k]);
                if(k>=w[i]&&(k==w[i]||f[i-1][j-1][k-w[i]]>0))f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-w[i]]+v[i]);
                if(k>=c)ans=max(f[i][j][k],ans);
            }
        }
    }
    printf("%dn",ans<=0?-1:ans);
} 

看球泡妹子


 42.选学霸

题目链接

这题....其实直接就是用并查集把所有实力相当的人统计一下,之后开一个桶存一下,统计后去不去重无所谓,去重后会快一点

之后做一下01背包就行了:$if(j-a[i])dp[j]=1$

澳门娱乐6165 83澳门娱乐6165 84

#include <bits/stdc++.h>
using namespace std;
#define N 20010
int n,m,k;
int f[N],cnt[N];
int tot,a[N];
bool dp[N];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        int u=find(x),v=find(y);
        f[v]=u;
    }
    for(int i=1;i<=n;i++)f[i]=find(f[i]);
    for(int i=1;i<=n;i++){
        cnt[f[i]]++;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        if(cnt[i]){
            a[++tot]=cnt[i];
        }
    }
    dp[0]=1;
    for(int i=1;i<=tot;i++){
        for(int j=n;j>=a[i];j--){
            if(dp[j-a[i]])dp[j]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(dp[i]&&abs(ans-m)>abs(i-m))ans=i;
    }
    printf("%dn",ans);
}

选学霸


 43.字串距离

题目链接

难度适中,很考验初始化的细节

设$f[i][j]$表示选了a串前i个字符 和b串前j个字符的最优解 

那么就可以分成选a,选b,ab都选3种情况来讨论

但是初始化很重要!

如果一直只选一个串,那么距离是i*k的!要初始化出来

澳门娱乐6165 85澳门娱乐6165 86

#include <bits/stdc++.h>
using namespace std;
char a[2000],b[2000];
int f[2000][2000],k,n,m;
//f[i][j]表示选了a串前i个字符 和b串前j个字符的最优解 
int main(){
    scanf("%s%s",a+1,b+1);
    scanf("%d",&k);
    n=strlen(a+1);m=strlen(b+1);
    for(int i=1;i<=n;i++)f[i][0]=i*k;
    for(int j=1;j<=m;j++)f[0][j]=j*k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=0x3f3f3f3f;
            f[i][j]=min(f[i][j],f[i-1][j-1]+abs(a[i]-b[j]));
            f[i][j]=min(f[i][j],min(f[i-1][j]+k,f[i][j-1]+k));
        }
    }
    printf("%dn",f[n][m]);
}

字串距离


 44.传球游戏

题目链接

怎么说呢...这题更像是递推,不是很像dp...

设$f[i][j]$表示球在i手上时一共传了j次

初始化$f[1][0]=1$

对于每个点显然它的答案是左右两边的人的答案之和,但是这样会有后效性...后面的状态你还没有算到呢...

怎么解决这个问题?把循环的顺序倒一下,从次数开始枚举,那么就不会有后效性啦

转移方程:$f[i][j]=f[(i==n?1:i+1)][j-1]+f[(i==1?n:i-1)][j-1]$

因为有环所以需要判一下

澳门娱乐6165 87澳门娱乐6165 88

#include <bits/stdc++.h>
using namespace std;
int f[100][100];
//传到第i个人,是第j次传 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    f[1][0]=1;
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[(i==n?1:i+1)][j-1]+f[(i==1?n:i-1)][j-1];
        }
    }
    printf("%dn",f[1][m]);
    return 0;
}

传球游戏


 45.积木城堡

题目链接

这题...还是套路题,对每个城堡做一遍01背包,然后开个桶存一下能组成的状态,最后从后往前扫一遍找到一个值为n的就是结果

澳门娱乐6165 89澳门娱乐6165 90

#include <bits/stdc++.h>
using namespace std;
int cnt[10000],f[10000],a[1000];
int x,sum,tot,n,m=0;
int main(){
    scanf("%d",&n);
    for(int kase=1;kase<=n;kase++){
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        sum=tot=0;
        f[0]=1;
        while(scanf("%d",&a[++tot])&&a[tot]!=-1)sum+=a[tot];
        tot--;m=max(m,sum);
        for(int i=1;i<=tot;i++){
            for(int j=sum;j>=a[i];j--){
                if(f[j-a[i]]&&!f[j]){
                    f[j]=1;cnt[j]++;
                }
            }
        }
    }
    for(int i=m;i;i--){
        if(cnt[i]==n){
            printf("%dn",i);
            return 0;
        }
    }
    return puts("0"),0;
}

积木城堡


 46.字符串折叠

题目链接

有难度的区间dp...专门写了一篇

题解传送门


 47.UVA1025 A Spy in the Metro

题目链接

洛谷有翻译我就不讲题意了...这是紫书里面的题

设$f[t][i]$表示时刻t时在i车站最少还要等多久

那么可以开个数组来表示时刻i在j车站有没有车,如果有,那么是向左还是向右

$train[t][i][0]$表示这个时刻有没有向右的车,$train[t][i][1]$同理,表示向左

转移方程倒是挺容易想,就是这个train数组的处理我没想到...翻了下紫书才知道怎么搞

转移方程

k表示时间,i表示车站,注意要倒序枚举时间

$f[k][i]=f[k+1][i]+1$

$f[k][i]=min(f[k+t[i]][i+1],f[k][i])$

$f[k][i]=min(f[k+t[i-1]][i-1],f[k][i])$

初始化$f[T][n]=0$

澳门娱乐6165 91澳门娱乐6165 92

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int f[300][60],t[100],T;
//时刻t在i车站的最优解 
bool train[399][100][2];
//0向右,1向左 
int main(){
    int n,kase=0;
    while(scanf("%d",&n)==1&&n){
        memset(train,0,sizeof(train));
        memset(f,0,sizeof(f));
        memset(t,0,sizeof(t));
        scanf("%d",&T);
        for(int i=1;i<n;i++)scanf("%d",&t[i]);
        int m1,m2;
        scanf("%d",&m1);
        for(int i=1;i<=m1;i++){
            int x;
            scanf("%d",&x);
            for(int j=1;j<=n;j++){
                train[x][j][0]=1;
                x+=t[j];
            }
        }
        scanf("%d",&m2);
        for(int i=1;i<=m2;i++){
            int x;
            scanf("%d",&x);
            for(int j=n;j>=1;j--){
                train[x][j][1]=1;
                x+=t[j-1];
            }
        }
        for(int i=1;i<n;i++)f[T][i]=inf;
        f[T][n]=0;
        for(int k=T-1;k>=0;k--){
            for(int i=1;i<=n;i++){
                f[k][i]=f[k+1][i]+1; 
                if(i<n&&train[k][i][0]&&k+t[i]<=T){
                    f[k][i]=min(f[k+t[i]][i+1],f[k][i]);
                }
                if(i>1&&train[k][i][1]&&k+t[i-1]<=T){
                    f[k][i]=min(f[k+t[i-1]][i-1],f[k][i]);
                }
            }
        }
        printf("Case Number %d: ",++kase);
        if(f[0][1]>=inf)puts("impossible");
        else printf("%dn",f[0][1]);
    }
}

uva1025


 48.传纸条

题目链接

简单dp...直接上四维就可以了...

也可以写三维但是四维就能过了

设$f[i][j][k][l]$表示第一张纸条传到i,j,第二张纸条传到k,l

转移方程

$f[i][j][k][l]=max(f[i][j-1][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k][l-1],f[i-1][j][k-1][l])))+a[i][j]+a[k][l]$

注意为了两条的路线不交集所以最后一位要从j+1开始枚举

澳门娱乐6165 93澳门娱乐6165 94

#include <bits/stdc++.h>
using namespace std;
int n,m,a[100][100],f[51][51][51][51];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=n;k++){
                for(int l=j+1;l<=m;l++){
                    f[i][j][k][l]=max(f[i][j-1][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k][l-1],f[i-1][j][k-1][l])))+a[i][j]+a[k][l];
                }
            }
        }
    }
    printf("%dn",f[n][m-1][n-1][m]);
}

传纸条


 49.书本整理

题目链接

挺基础的一个dp

设$f[i][j]$表示前i本书选了j本,且以第i本结尾的最优解

那么$f[i][j]=min(f[i][j],f[k][j-1]+abs(a[i].w-a[k].w))$

初始化就是$f[i][1]=0$

澳门娱乐6165 95澳门娱乐6165 96

#include <bits/stdc++.h>
using namespace std;
struct node {
    int h,w;
}a[1000];
int f[110][110],n,k;
//前i本书选了j本且以第i本结束 
bool cmp(node a,node b){
    return a.h<b.h;
}
#define inf 0x3f3f3f3f
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].h,&a[i].w);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        f[i][1]=0;
        for(int j=2;j<=i;j++){
            f[i][j]=inf;
            for(int k=j-1;k<i;k++){
                f[i][j]=min(f[i][j],f[k][j-1]+abs(a[i].w-a[k].w));
            }
        }
    }
    int ans=inf;
    for(int i=n-k;i<=n;i++){
        ans=min(f[i][n-k],ans);
    }
    printf("%dn",ans);
}

书本整理


 50.[Zjoi2004]Lunch 午餐

题目链接

最后一题了来道难题(滑稽

不过这题不看题解我想不出来...只能想到一个空间爆炸的做法

照例是专门写了个题解:题解传送门


50题了!

完结撒花!

>_<!

没有未完待续!

填坑感想?开坑真的好累啊...我从6月开的这坑补到8月31....整整3个月...

 

本文由澳门娱乐6165发布,转载请注明来源

关键词: