A - 上台阶2

小瓜一次只能向上走1级或者3级或者5级台阶
问： 有多少种方法走上n阶台阶

#include<iostream>
using namespace std;
long step[1000003] = {0};
int main(){int N;cin>>N;if(N<=0){return 0;}step[0] = 1;step[1] = 1;step[2] = 2;step[3] = 3;step[4] = 5;if(N<=5){cout<<step[N-1]<<endl;return 0;}for(int i=5;i<N;i++){step[i]= (step[i-1]+step[i-3]+step[i-5])%100003;}cout<<step[N-1]<<endl;
}

B - 数字三角形

一个数字三角形。从三角形的顶部到底部有很多条不同的路径，把路径上面的数加起来找到最大的和
注：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数

#include<bits/stdc++.h>
using namespace std;const int N=510;
int maxs[N][N];
int f[N][N];
int n;
void dp(){for(int i=1;i<=n;i++) maxs[n][i]=f[n][i];for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){maxs[i][j]=max(maxs[i+1][j],maxs[i+1][j+1])+f[i][j];}}
}
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>f[i][j];}}dp();cout<<maxs[1][1]<<endl;
}

C - 矩阵取数问题

N*N矩阵中有不同的正整数 ，从左上走到右下，只能向下向右走，求能够获得的最大价值

#include<stdio.h>
#include<iostream>
using namespace std;
long long dp[510][510];
int main()
{int N,s[510][510];scanf("%d",&N);for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){scanf("%d",&s[i][j]);}}/* for(int i=0;i<=N;i++){for(int j=0;j<=N;j++){dp[i][j]=-1;}}防止矩阵中有负数*/ dp[1][1]=s[1][1];for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1])+s[i][j]);}}printf("%lld\n",dp[N][N]);return 0;
}

D - 背包问题（01背包）

每种物品仅选一个

#include<bits/stdc++.h>using namespace std;const int MAXN = 10005;
int f[MAXN];  // int main() 
{int n, m;   cin >> n >> m;for(int i = 1; i <= n; i++) {int v, w;cin >> v >> w;      // 边输入边处理for(int j = m; j >= v; j--)   //  v 体积  w  价值  m 最大容量f[j] = max(f[j], f[j - v] + w);}cout << f[m] << endl;return 0;
}

E - 完全背包

每种物品可选任意个

#include<iostream>
using namespace std;const int N = 50010;int n, m;
int dp[N];int main(){cin >> n >> m;for(int i = 1; i <= n; i ++ ){int v, w;cin >> v >> w;  // v 物品体积   w 价值for(int j = v; j <= m; j ++ ){ dp[j] = max(dp[j], dp[j - v] + w);}}cout << dp[m] << endl;
}

F - 背包问题 V2 (多重背包）

每种物品的数量是有限个
注： 可将每个输入的物品 划分为01 背包 即 体积数组 价值数组
也可加上此物品的循环 多次判断此物

//  在01背包基础上  多次判断此物品
#include <bits/stdc++.h>
using namespace std;
int dp[50015],n,t,v,w,s;
main()
{cin>>n>>t;while(n--){cin>>w>>v>>s;   // w 体积  v 价值  s 数量for(int i=1;i<=s;i++)for(int j=t;j>=w;j--)    //t 最大容量dp[j]=max(dp[j],dp[j-w]+v);}cout<<dp[t];
}

#include <bits/stdc++.h>
using namespace std;
int a[50005],b[50005],t=0,n,m,dp[50015]={ },w,v,s;
int main()
{cin>>n>>m;while(n--){cin>>v>>w>>s;while(s--){a[++t]=v;     // a 体积   b  价值b[t]=w;}//死拆，把多重背包拆成01背包}for(int i=1;i<=t;i++)for(int j=m;j>=a[i];j--)dp[j]=max(dp[j-a[i]]+b[i],dp[j]);//直接套01背包的板子cout<<dp[m]<<endl;return 0;
}        

G - 最长上升子序列

对于给定的序列，求出最长上升子序列的长度
f[i] 为 第i个数为止的上升子序列的长度 （包括第i个数）

#include <iostream>
using namespace std;
const int N = 1010;
int n;
int w[N], f[N];
int main() {cin >> n;for (int i = 0; i < n; i++) cin >> w[i];int mx = 1;    // 找出所计算的f[i]之中的最大值，边算边找for (int i = 0; i < n; i++) {f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1for (int j = 0; j < i; j++) {if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);    // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1}mx = max(mx, f[i]);}cout << mx << endl;return 0;
}

H - 最长公共子序列Lcs

给出两个字符串A B，求A与B的最长公共子序列（A,B的长度 <= 1000，子序列不要求是连续的）。
比如两个串为：
A：abcicba B：abdkscab
ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。。
Input
第1行：字符串A 第2行：字符串B
Output
输出最长的子序列，如果有多个，随意输出1个。
Sample
Input
abcicba
abdkscab
Output
abca

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int dp[N][N];
int main()
{cin>>a+1>>b+1;int la=strlen(a+1),lb=strlen(b+1);for(int i=1;i<=la;i++)for(int j=1;j<=lb;j++){dp[i][j]=max(dp[i][j-1],dp[i-1][j]);if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);}int pos1=la,pos2=lb;stack<char>st;while(pos1>0&&pos2>0){if(a[pos1]==b[pos2]){st.push(a[pos1]);pos1--;pos2--;}else if(dp[pos1][pos2]==dp[pos1-1][pos2])pos1--;else pos2--;}while(!st.empty()){cout<<st.top();st.pop();}return 0;
}

I - 石子合并

#include <iostream>
#include <cstring>using namespace std;const int N = 210, M = N << 1, INF = 0x3f3f3f3f;int n;
int w[M], s[M];
int f[M][M], g[M][M];int main()
{//读入scanf("%d", &n);for (int i = 1; i <= n; ++ i) cin >> w[i], w[i + n] = w[i];//预处理前缀和（DP状态转移中会频繁的用到区间和）for (int i = 1; i <= n << 1; ++ i) s[i] = s[i - 1] + w[i];memset(f, -0x3f, sizeof f);//求最大值预处理成最小值（可以省掉，这题不会有负数状态所以0就是最小）memset(g, +0x3f, sizeof g);//求最小值预处理成最大值（不可省掉）for (int len = 1; len <= n; ++ len)//阶段{for (int l = 1, r; r = l + len - 1, r < n << 1; ++ l)//左右区间参数{if (len == 1) f[l][l] = g[l][l] = 0;//预处理初始状态else{for (int k = l; k + 1 <= r; ++ k)//枚举分开点{f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]),g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);}}}}//目标状态中找出方案int minv = INF, maxv = -INF;for (int l = 1; l <= n; ++ l){minv = min(minv, g[l][l + n - 1]);maxv = max(maxv, f[l][l + n - 1]);}//输出printf("%d\n%d\n", minv, maxv);return 0;
}

J - 循环数组最大子段和

最大字段和循环序列有两种情况，
一是中间某部分和最大，无跨越情况，如 -1 2 3 5 -2，最大和是10，
另一种情况是由首尾两段组成如 3 5 -100 -200 1，最大和为9。只需求出中间部分的最小值，然后用数组所有元素和减去即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N];
ll s,ans=-1e18,ans1=1e18,sum,s1;int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}for(int i=1;i<=n;i++){if(s1>0)s1=0;if(s<0)s=0;  小于0  归0即可s+=a[i];// 大于0 只管加即可  s1+=a[i];ans=max(ans,s);ans1=min(ans1,s1);// 计算中间某部分的最小和}ans=max(ans,sum-ans1);  //sum -中间最小和= 首尾处最大和cout<<ans;
}

K - 没有上司的舞会— 树形dp入门

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
int happy[N];
bool has_fa[N];
int  dp[N][2];
int e[N],h[N],ne[N],idx;
vector<int>link[N];
queue<int>q;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u)
{dp[u][1]=happy[u];for(int i=h[u];~i;i=ne[i]){int j=e[i];dfs(j);dp[u][0]+=max(dp[j][0],dp[j][1]);dp[u][1]+=dp[j][0];}
}int main()
{int n;cin>>n;memset(h,-1,sizeof h);for(int i=1;i<=n;i++)scanf("%d",&happy[i]);for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);link[a].push_back(b);link[b].push_back(a);}q.push(1);has_fa[1]=1;while(q.size()){int t=q.front();q.pop();for(int i=0;i<link[t].size();i++){if(!has_fa[link[t][i]]){int tmp=link[t][i];q.push(tmp);has_fa[tmp]=1;add(t,tmp);}}}dfs(1);cout<<max(dp[1][0],dp[1][1])<<endl;return 0;
}

L - 滑雪
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample
Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Output
25

include<bits/stdc++.h>
using namespace std;const int N=110;int dp[N][N],a[N][N];
int n,m,ans;struct node
{int i,j,num;bool operator<(const node &t) const{return num>t.num;}
};priority_queue<node>q; 
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];q.push({i,j,a[i][j]});dp[i][j]=1;}while(q.size()){auto t=q.top();q.pop();int i=t.i,j=t.j;if(a[i-1][j]<a[i][j])dp[i][j]=max(dp[i-1][j]+1,dp[i][j]);if(a[i+1][j]<a[i][j])dp[i][j]=max(dp[i+1][j]+1,dp[i][j]);if(a[i][j-1]<a[i][j])dp[i][j]=max(dp[i][j-1]+1,dp[i][j]);if(a[i][j+1]<a[i][j])dp[i][j]=max(dp[i][j+1]+1,dp[i][j]);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=max(ans,dp[i][j]);cout<<ans<<endl;
}