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

dp总结：https://www.cnblogs.com/henry-1202/p/9194066.html

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

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

1.合唱队形

题目链接

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

使用O(n²)做法即可

#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.O(n²)做法

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

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

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

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

#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做法

2.O(nlogn)做法

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

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

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

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

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

#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做法

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就好

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

#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;
}

尼克的任务

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]$（不休息，直接从头走到尾）

代码

#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;
}

丝绸之路

5.分队问题

题目链接

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

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

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

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

来一组数据

2 3 3 3

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

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

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

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

那么来想想dp做法

设

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

所以可以得到一个转移方程：

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

考虑怎么去优化它

我们可以开一个数组来储存

则转移方程可以改成：

对于g数组的维护：

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

#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;
}

分队问题

6.低价购买

题目链接

第一问直接n²做法求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

#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;
}

低价购买

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])$

#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;
}

回文字串

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)$做法

#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(n²)$，因为这题的数据范围不大，如果大的话就最好开一下双hash/三hash/自然溢出hash

#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])$

#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;
}

创意吃鱼法

#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次...

#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: %d\n",k,m);
    }
    return 0;
}

UVA10635

12.木棍加工

题目链接

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

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

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

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

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

#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("%d\n",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并没有再回去

#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("%d\n",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种电灯泡全用这种类型的灯泡所需的价格

#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("%d\n",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]$

#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("impossible\n");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("%d\n",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不然会爆

#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("%lld\n",f[m][n]);
    return 0;
}

最佳课题选择

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

17.[USACO06FEB]奶牛零食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))$

#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])

#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("%d\n",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]$

#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("%d\n",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头狼时最后杀死的那头狼）

#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: %lld\n",++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)$了

#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("%d\n",ans);
    return 0;
}

n^3

#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("%d\n",ans);
    return 0;
}

n^2

23.乌龟棋

啊挺简单的一道dp

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

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

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

就直接dp下去就行了

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

#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("%d\n",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]$

#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("%d\n",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$的情况并不适用，需要特判

#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("%d\n",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("%d\n",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)$

#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("%d\n",f[1]);
    return 0;
}

牛的词汇

27.[USACO07MAR]牛交通Cow Traffic

题目链接

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

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

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

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

#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("%d\n",ans);
    return 0;
}

牛的交通

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

题目链接

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

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

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

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

#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("%d\n",ans);
}

挤奶时间

29.装箱问题

题目链接

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

#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("%d\n",v-f[v]);
}

装箱问题

30.[HNOI2004]打鼹鼠

题目链接

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

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

#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("%d\n",ans);
}

[HNOI2004]打鼹鼠

31.道路游戏

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

传送门

32.[CQOI2007]涂色

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

题解传送门

33.[BeijingWc2008]雷涛的小猫

简单dp，优化一下就能过

WC居然有这种简单题？！

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

传送门

34.教主的花园

题目链接

好麻烦的一个dp...

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

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

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

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

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

#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("%d\n",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，不然第十四个点排序的时候会爆掉...

#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("%lld\n",ans);
    return 0;
}

烹调方案

36.经营与开发

题目链接

有点思维难度...

正推有后效性所以倒推

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

#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("%.2lf\n",f[1]*w);
}

经营与开发

37.货币系统

题目链接

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

#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("%lld\n",dp[m]);
}

货币系统

38.[HAOI2012]音量调节

题目链接

比较神奇的背包...

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

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

#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("%d\n",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]$

具体细节看代码吧

#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 %d\n",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("%d\n",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])$

输出路径递归输出就行

#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("%d\n",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$不预处理直接算也行

#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("%d\n",ans<=0?-1:ans);
}

看球泡妹子

42.选学霸

题目链接

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

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

#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("%d\n",ans);
}

选学霸

43.字串距离

题目链接

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

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

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

但是初始化很重要！

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

#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("%d\n",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]$

因为有环所以需要判一下

#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("%d\n",f[1][m]);
    return 0;
}

传球游戏

45.积木城堡

题目链接

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

#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("%d\n",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$

#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("%d\n",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开始枚举

#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("%d\n",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$

#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("%d\n",ans);
}

书本整理

50.[Zjoi2004]Lunch 午餐

题目链接

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

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

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

50题了！

完结撒花！

>_<！

没有未完待续！

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

dp专题练习

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

1.合唱队形

2.导弹拦截

1.O(n2)做法

2.O(nlogn)做法

3.尼克的任务

4.丝绸之路

5.分队问题

6.低价购买

7.回文字串

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

9.魔族密码

10.创意吃鱼法

11.UVA10635 Prince and Princess

12.木棍加工

13.[USACO08MAR]跨河River Crossing

14.UVA11400 Lighting System Design

15.出租车拼车

16.最佳课题选择

17.[USACO06FEB]奶牛零食Treats for the Cows

18.能量项链

19.跳房子

20.摆花

21.HDU5115

22.[USACO13NOV]POGO的牛Pogo-Cow

23.乌龟棋

24.[USACO08JAN]跑步Running

25.过河

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

27.[USACO07MAR]牛交通Cow Traffic

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

29.装箱问题

30.[HNOI2004]打鼹鼠

31.道路游戏

32.[CQOI2007]涂色

33.[BeijingWc2008]雷涛的小猫

34.教主的花园

35.烹调方案

36.经营与开发

37.货币系统

38.[HAOI2012]音量调节

39.机器分配

40.花店橱窗布置

41.看球泡妹子

42.选学霸

43.字串距离

44.传球游戏

45.积木城堡

46.字符串折叠

47.UVA1025 A Spy in the Metro

48.传纸条

49.书本整理

50.[Zjoi2004]Lunch 午餐

1.O(n²)做法