dp

P1048 [NOIP2005 普及组] 采药

dp入门题，可以二维做也可以一维做，一维做的时候要倒着做，正着做可能会被一个药物更新好几次，完全背包。

// luogu-judger-enable-o2
#include "iostream"
#include "stdio.h"
using namespace std;
int w[105],val[105];
int dp[105][1005];
int main()
{
    int t,m,res=-1;
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&w[i],&val[i]);
    }
    for(int i=1;i<=m;i++) 
        for(int j=t;j>=0;j--)  
        {
            if(j>=w[i])
            {
                dp[i][j]=max(dp[i-1][j-w[i]]+val[i],dp[i-1][j]);
            }  
            else
            {
                dp[i][j]=dp[i-1][j];
            }              
        }
    printf("%d",dp[m][t]);
    return 0;
}

B3637 最长上升子序列

数据范围，n^2是刚刚好，就不用二分单调优化了
if(a[i] > a[j] )f[i] = max(f[i] , f[j] + 1 )
1 <= j <= i - 1

#include<bits/stdc++.h>
using namespace std;
long long f[5001];
int n ;
int a[5002]; 
int main () {
	cin >> n ;
	for(int i = 1; i <= n ; i ++){
		cin >> a[i];
		f[i] = 1;
	}
	long long ans = 0; 
	for(int i = 1;  i <= n ; i ++){
		for(int j = 1 ;j < i ; j ++){
			if(a[j] < a[i]){
				f[i] = max(f[i] , f[j] + 1);
			}
			ans = max(ans , f[i]); 
		}
	}
	cout << ans << endl;
}

P1115 最大子段和

继续留恋，还是开启下一段

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
int n , x , z, s;
int main() { 
z =  -100000000;
scanf("%d",&n); 
	for (int i = 0; i< n ; i++){
		scanf ("%d", &x);
		s = max(s + x , x);
	    z  =  max (z , s); 
 	}
cout << z ;
}

P1115 最大子段和

就是最长公共子序列的板子，最后找路径也就是把dp的过程逆了过去。

#include<bits/stdc++.h> 
using namespace std;
int f[3010][3010];
char s1[100010], s2[100010], ans[1000010];
int main()
{
    cin >> s1 + 1 >> s2 + 1; 
   	int len1 = strlen(s1 + 1);
	int len2 = strlen(s2 + 1);
	for(int i = 1; i <= len1; i++)
	{
		for(int j = 1; j <= len2; j++)
		{
	    	f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if(s1[i] == s2[j])
            {
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
		}
	}
	int i = len1, j = len2;
	while(f[i][j] > 0)
    {
		if(s1[i] == s2[j])
        {
            ans[f[i][j]] = s1[i];
            i--, j--;
        }
		else
        {
			if(f[i][j] == f[i - 1][j]) i--;
			else j--;
		}
	}
	cout << ans + 1 << endl;
	return 0;
}