基础部分

P1002 [NOIP2002 普及组] 过河卒

dp方程:因为小兵只能往下或者右走,我们设一个二维dp数组dp[i][j]表示从起点到坐标为(i,j)的路径数,如果这个点能被马能吃掉的,那就dp[i][j]=0,这个可以告诉它下面和右边的点,我这是不能到达的.然后输出dp[N][M]就行了

#include&lt;stdio.h>
#include&lt;iostream>
#include&lt;algorithm>
#include&lt;vector>
#include&lt;stack>
#include &lt;math.h>
using namespace std;
#define N 40
int t[N];
int a[N][N];
long long dp[N][N];
bool beimalanzhu[N][N]; //判断这个点有没有马拦住
const int madex[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int madey[] = {1, 2, 2, 1, -1, -2, -2, -1};
int c,n;
//long long count(long long a,long long b,long long p){
//    if(b==0) return 1;
//    if(b==1) return a%p;
//    long long c = count(a,b/2,p)%p;
//    return ((b%2==0?1:a)*c*c)%p;
//}

int main(){
    int ma_x,ma_y;
    int b_x,b_y;
    scanf("%d %d %d %d",&amp;b_x,&amp;b_y,&amp;ma_x,&amp;ma_y);
    ma_x+=2;
    ma_y+=2;
    b_x+=2;
    b_y+=2;
    
    dp[2][1]=1;
    for(int i=0;i&lt;8;i++){
        beimalanzhu[ma_x+madex[i]][ma_y+madey[i]]=true;
    }
    //忘记讨论马自己了
    beimalanzhu[ma_x][ma_y] = true;
    for(int i=2;i&lt;=b_x;i++){
        for(int j=2;j&lt;=b_y;j++){
            if(beimalanzhu[i][j]) continue;
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    printf("%lld",dp[b_x][b_y]);
}

P1095 [NOIP2007 普及组] 守望者的逃离

这个其实我们都知道,根据中学物理的知识都知道我们瞬移最好,但是有这么一种情况,就是你瞬移没蓝了,但是终点离你不远,这时候还不如直接开跑,等在这里等蓝还不如直接run
这个时候就有个最优选择了:维护一个一维的dp数组dp[T]来表示到t时间最远能run多远,那我们假设一个dp[t],dp[1,….t-1]都是已知的了,那就可以维护了dp[t]=max[dp[t-1]+17,r[t]],r[t]就代表一直瞬移的距离,如果这个时候一直瞬移还不如现在直接跑来得快,那就选跑

对于这位可怜的人,一直闪现肯定是最优解,但是这里dp其实判断的是,对于这个时刻,没有蓝了,是停在原地回蓝好还是直接撒腿就跑好,是判断这俩的选择的.

#include&lt;stdio.h&gt;
#define N 300005
int dp[N];
int main(){
    int M,S,T;
    scanf("%d %d %d",&amp;M,&amp;S,&amp;T);
    dp[0]=0;
    int run;
    int flash;
    for(int i=1;i&lt;=T;i++){
        if(M&gt;=10) {
            dp[i]=dp[i-1]+60;
            M-=10;
        }
        else{
            dp[i]=dp[i-1];
            M+=4;
        }
        
    }
    for(int i=1;i&lt;=T;i++){
        if(dp[i]&lt;dp[i-1]+17) dp[i]=dp[i-1]+17;
        if(dp[i]&gt;S){
            printf("Yes\n%d",i);
            return 0;
        }
    }
    printf("No\n%d",dp[T]);
    
}

背包

P1048 [NOIP2005 普及组] 采药

动态规划方程

#include "iostream"
#include "stdio.h"
using namespace std;
int  weigth[105],value[105];
//dp[i][j]代表处理第i个,背包容量还剩下j个
int dp[105][1005];
int total,m;

int main(){
    scanf("%d %d",&amp;total,&amp;m);
    for(int i=1;i&lt;=m;i++){
        scanf("%d %d",&amp;weigth[i],&amp;value[i]);
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=total;j&gt;=0;j--){
            //表示这个元素可以选入
            if(j&gt;=weigth[i]){
                dp[i][j]=max(dp[i-1][j-weigth[i]]+value[i],dp[i-1][j]);
            }
            //不可以
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    printf("%d",dp[m][total]);
}

P1616 疯狂的采药

一维dp数组,dp[m]代表用m的背包就可以获得的最大元素,还是两层循环,外循环是对物品种类进行讨论,内循环对dp方程进行处理,看看对于一个重量 $j$ ,我要不要选择第 $i$ 号元素放入背包中.

#include<stdio.h>;
#include<iostream&gt;
#include<algorithm&gt;
using namespace std;
const int M = 1e7+5;
long long  weigth[M],value[10005];
//dp[i][j]代表处理第i个,背包容量还剩下j个
long long dp[M];
long long total,m;

int main(){
    scanf("%lld %lld",&amp;total,&amp;m);
    for(int i=1;i&lt;=m;i++){
        scanf("%lld %lld",&amp;weigth[i],&amp;value[i]);
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=weigth[i];j&lt;=total;j++){
            dp[j]=max(dp[j],dp[j-weigth[i]]+value[i]);
        }
    }
    printf("%lld",dp[total]);
}

线性

P1091 [NOIP2004 提高组] 合唱队形

这是一个脑筋急转弯类型的题目,第一步就是计算[1,i]的最长上升子序列的长度,记在dp[i][0]中,第二步就是计算[i,n]的最长下降子序列的长度,记在dp[i][1].但是有一点就是这个最长上升子序列长度是要包括自己的.
记dp1[i]=dp[i][0]+dp[i][1]
最后的结果就是需要找到一个点使得dp1[i]最大,这样就代表这个点左右更加光滑.

#include&lt;stdio.h&gt;
#define N 105
int a[N];
int dp[N][2];
int res[N];
//dp数组,dp[i][0]
int main(){
    int n;
    scanf("%d",&amp;n);
    for(int i=1;i&lt;=n;i++){
        scanf("%d",&amp;a[i]);
        
    }
    //从左到右扫描
    for(int i=2;i&lt;=n;i++){
        for(int j=1;j&lt;i;j++){
            if(a[i]&gt;a[j]&amp;&amp;dp[i][0]&lt;=dp[j][0]+1){
                dp[i][0]=dp[j][0]+1;
            }
        }
    }
    for(int i=n-1;i&gt;=1;i--){
        for(int j=i+1;j&lt;=n;j++){
            if(a[i]&gt;a[j]&amp;&amp;dp[i][1]&lt;=dp[j][1]+1){
                dp[i][1]=dp[j][1]+1;
            }
        }
    }
    int result=0;
    for(int i=1;i&lt;=n;i++){
        res[i]=dp[i][0]+dp[i][1]+1;
        if(res[i]&gt;result) result=res[i];
    }
    printf("%d",n-result);
}

P1439 【模板】最长公共子序列

排列中没有重复元素，俩排列置换后 (重命名) 的 LCS 长度不变:不妨用置换 $\sigma$ 将排列 $P_1$ $\to$ [1:n].

这个时候我们可以将排列 $P_1$ 变成[1,2,3,….,n]然后排列 $P_2$ 映射成与 $P_1$ 相匹配的形式.排列 $P_2$ 中第 $i$ 个元素存储的就是原来的元素在 $P_1$ 中的位置

如图,Y中第一个元素5,在X中的位置是第6个.

这个时候变成求Y的最长上升子序列了

现在进行算法改进:

#include&lt;stdio.h&gt;
#include&lt;algorithm&gt;
#define N 100005
using namespace std;
int a[N],b[N],c[N],found[N];
int main(){
    int n;
    scanf("%d",&amp;n);
    for(int i=1;i&lt;=n;i++){
        scanf("%d",&amp;a[i]);
        c[a[i]]=i;
    }
    for(int i=1;i&lt;=n;i++){
        scanf("%d",&amp;b[i]);
        found[i]=114514;
    }
    int LCS_length=0;
    for (int i=1; i&lt;=n; i++) {
        int l=0,r=LCS_length,mid;
        //如果大于:直接放在后面
        if(c[b[i]]&gt;found[LCS_length]){
            found[++LCS_length]=c[b[i]];
        }
        //如果小于二分查找
        else{
            while (l&lt;r) {
                mid=(l+r)/2;
                if(found[mid]&gt;c[b[i]]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            found[l]=min(c[b[i]],found[l]);
        }
    }
    printf("%d\n",LCS_length);
}

区间

P1880 [NOI1995] 石子合并

让dp[i][j]代表第i堆到第j堆的合并分数,我们要做的事 $dp[i][i+n-1]$ 最大(小),只需要在区间[i][j]中找到一个最佳的分划k,让i-k,k+1,j这两个区域内部得分和合并这两个区域的得分最大(小),即 $max(a[i][k]+a[k+1][j]+d(i,j))$ 分别代表两个区域的分划和合并两部分的得分

#include<stdio.h>
#include<algorithm>
#define N 205
int mins[N][N];
int maxs[N][N];
int stones[N];
int sums[N];//前缀和
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&stones[i]);
        sums[i]=sums[i-1]+stones[i];
        stones[i+n]=stones[i];
    }
    for(int i=n+1;i<=2*n;i++){
        sums[i]=sums[i-1]+stones[i];
    }
    for(int length=1;length<n;length++){
        for(int i=1,j=i+length;j<2*n&&i<2*n;i++,j=length+i){
            mins[i][j]=1145141919;
            for(int k=i;k<j;k++){
                maxs[i][j]=std::max(maxs[i][j],maxs[i][k]+maxs[k+1][j]+sums[j]-sums[i-1]);
                mins[i][j]=std::min(mins[i][j],mins[i][k]+mins[k+1][j]+sums[j]-sums[i-1]);
            }
        }
    }
    int min_res=114514;
    int max_res=0;
    for(int i=1;i<=n;i++){
        max_res=std::max(max_res,maxs[i][i+n-1]);
        min_res=std::min(min_res,mins[i][i+n-1]);
    }
    printf("%d\n%d",min_res,max_res);
}

洛谷刷题记录(算法)