基础部分
P1002 [NOIP2002 普及组] 过河卒

dp方程:因为小兵只能往下或者右走,我们设一个二维dp数组dp[i][j]表示从起点到坐标为(i,j)的路径数,如果这个点能被马能吃掉的,那就dp[i][j]=0,这个可以告诉它下面和右边的点,我这是不能到达的.然后输出dp[N][M]就行了
#include<stdio.h> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include <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",&b_x,&b_y,&ma_x,&ma_y); ma_x+=2; ma_y+=2; b_x+=2; b_y+=2; dp[2][1]=1; for(int i=0;i<8;i++){ beimalanzhu[ma_x+madex[i]][ma_y+madey[i]]=true; } //忘记讨论马自己了 beimalanzhu[ma_x][ma_y] = true; for(int i=2;i<=b_x;i++){ for(int j=2;j<=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<stdio.h> #define N 300005 int dp[N]; int main(){ int M,S,T; scanf("%d %d %d",&M,&S,&T); dp[0]=0; int run; int flash; for(int i=1;i<=T;i++){ if(M>=10) { dp[i]=dp[i-1]+60; M-=10; } else{ dp[i]=dp[i-1]; M+=4; } } for(int i=1;i<=T;i++){ if(dp[i]<dp[i-1]+17) dp[i]=dp[i-1]+17; if(dp[i]>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",&total,&m); for(int i=1;i<=m;i++){ scanf("%d %d",&weigth[i],&value[i]); } for(int i=1;i<=m;i++){ for(int j=total;j>=0;j--){ //表示这个元素可以选入 if(j>=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方程进行处理,看看对于一个重量,我要不要选择第
号元素放入背包中.
#include<stdio.h>; #include<iostream> #include<algorithm> 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",&total,&m); for(int i=1;i<=m;i++){ scanf("%lld %lld",&weigth[i],&value[i]); } for(int i=1;i<=m;i++){ for(int j=weigth[i];j<=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<stdio.h> #define N 105 int a[N]; int dp[N][2]; int res[N]; //dp数组,dp[i][0] int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } //从左到右扫描 for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ if(a[i]>a[j]&&dp[i][0]<=dp[j][0]+1){ dp[i][0]=dp[j][0]+1; } } } for(int i=n-1;i>=1;i--){ for(int j=i+1;j<=n;j++){ if(a[i]>a[j]&&dp[i][1]<=dp[j][1]+1){ dp[i][1]=dp[j][1]+1; } } } int result=0; for(int i=1;i<=n;i++){ res[i]=dp[i][0]+dp[i][1]+1; if(res[i]>result) result=res[i]; } printf("%d",n-result); }
P1439 【模板】最长公共子序列




这个时候我们可以将排列







如图,Y中第一个元素5,在X中的位置是第6个.
这个时候变成求Y的最长上升子序列了

现在进行算法改进:



#include<stdio.h> #include<algorithm> #define N 100005 using namespace std; int a[N],b[N],c[N],found[N]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); c[a[i]]=i; } for(int i=1;i<=n;i++){ scanf("%d",&b[i]); found[i]=114514; } int LCS_length=0; for (int i=1; i<=n; i++) { int l=0,r=LCS_length,mid; //如果大于:直接放在后面 if(c[b[i]]>found[LCS_length]){ found[++LCS_length]=c[b[i]]; } //如果小于二分查找 else{ while (l<r) { mid=(l+r)/2; if(found[mid]>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堆的合并分数,我们要做的事最大(小),只需要在区间[i][j]中找到一个最佳的分划k,让i-k,k+1,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); }