王道机试 DP篇

LIS

72bf72d63670611052521b1c226bfb15

刚开始看讲解感觉理解困难，写了代码仿佛秒懂了，但是怎么构建这么个dp【用来存以ai结尾的LIS的最长长度，最后在for一遍找到全局最长的LIS】，还需要深入思考+总结

case1：拦截导弹，这就是LIS的镜像版本LDS？就是每次往前找>=当前位置的即可

#include
#include
using namespace std;
const int N=30;
int a[N];
int dp[N];//存每个以ai结果的最长递增子序列的元素数int main() {int n;while(cin>>n, n!=0) {memset(dp,0,sizeof(dp));for(int i=0; i=a[i]) {if(dp[j]+1>tmax)tmax=dp[j]+1;//这就是基于前面已经找到了的lIS，看能否在这基础上更“长”}}dp[i]=tmax;}int ans=-1;for(int i=0; ians)ans=dp[i];printf("%d\n", ans);}return 0;
}

case2：合唱队形，问一个序列要满足先增后减序列，最少要去掉几个数

#include
using namespace std;
const int N=105;
int a[N];
int dp1[N],dp2[N];//正向上升，反向上升！
int main() {//17:41->sint n,ma;while(scanf("%d",&n)!=EOF, n) {for(int i=0; i=0; i--) {ma=1;for(int j=n-1; j>i; j--) {if(a[j]ma)ma=dp1[i]+dp2[i];}printf("%d\n", n-ma+1);}return 0;
}

LCS

case1：裸的LCS，以下为标准版子，几个细节

#include
using namespace std;
const int N=105;
string a,b;
int dp[N][N];//dp[i][j]表示a和b在前i和j个字符时的LCS长度
int main() {while(cin>>a>>b) {int la=a.length();int lb=b.length();for(int i=0; i<=la; i++) dp[i][0]=0; //共la+1个数要initfor(int j=0; j<=lb; j++) dp[0][j]=0;for(int i=1; i<=la; i++) {//1~lafor(int j=1; j<=lb; j++) {if(a[i-1]==b[j-1])//把i-1当做上次位置，每次递推当前的i位置dp[i][j]= dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i][j-1], dp[i-1][j]);}}printf("%d\n", dp[la][lb]);}return 0;
}

背包

01背包：每个物品选1或不选。二维的情况好理解多了，dp[i][j]为选到前i个物品时剩余容量j时的最大收益，就是从头开始填表。注意

#include
using namespace std;
const int N=1005;
int w[N];//重量
int v[N];//收益
int dp[N][N];//dpij表示体积<=j时，前i个物品达到的最大收益
int W,n;//容量，物品数
void show_dp() {for(int i=1; i<=n; i++) {for(int j=0; j<=W; j++)cout<>W>>n) {if(!W && !n) break;for(int i=1; i<=n; i++)//必须从1开始，因为0有“没选物品”的含义，不能缺少！cin>>w[i]>>v[i];for(int j=0; j<=W; j++) dp[0][j]=0;//没选的话，都是0 for(int i=1; i<=n; i++) {for(int j=w[i]; j<=W; j++)//够装 dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);for(int j=w[i]-1; j>=0; j--)//不够装 dp[i][j]=dp[i-1][j];
//			show_dp();}cout<

#include
using namespace std;
const int N=1005;
int w[N];//重量
int v[N];//收益
int dp[N];//体积<=j时，能达到的最大收益
int W,n;//时间，物品数
void show_dp() {for(int j=0; j<=W; j++)cout<>W>>n) {if(!W && !n) break;for(int i=1; i<=n; i++)//必须从1开始，因为0有“没选物品”的含义，不能缺少！cin>>w[i]>>v[i];for(int j=0; j<=W; j++) dp[j]=0; //也要都init=0。理解为，虽把时间维度去了，//但是其实刚开始是要全部赋为0，表示了时间维度的意义，即“没选”时，收益都是0for(int i=1; i<=n; i++) {for(int j=w[i]; j<=W; j++)dp[j]=max(dp[j], dp[j-w[i]]+v[i]);show_dp();}cout<