A - （最长公共子序列模板） POJ - 1458
# include<iostream>
# include<algorithm>
# include<cstring>
using namespace std;
const int N = 555;
char a[N], b[N];
int main()
{
while(cin>>a+1>>b+1) //读入字符串a，b
{
int dp[N][N]; //定义答案数组dp
//dp[i][j]是字串a的前i个字符与字串b的前j个字符的最长公共子序列
int n = strlen(a+1), m = strlen(b+1);
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++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);
//如果最后两个字串的最后一个数相同，最长公共子序列可能为a前i-1个字符与b的前j-1个字符的最长公共子序列再+1
}
}
cout<<dp[n][m]<<endl; //根据定义，输出答案
}
return 0;
}
B - （思维？） HDU - 1003
主要思想：如果当前连续子序列的值为正值，那么无论它再加任何数，其总值都会大于它要加的数；如果当前连续子序列的值为负数，那么无论它再加任何数，其总值都会小于它要加的数。因此只有当当前子序列为正值的时候，该连续子序列的值才有可能增加，若为负数，则一定减小。所有当连续子序列的值为负数时，及时舍去该序列，重新再开一段序列（新序列的初始总值为0）
# include<iostream>
# include<cstring>
using namespace std;
const int N = 1e5+10;
struct Num
{
int num, val;
}mini;
int t;
int a[N], s[N];
int main()
{
cin>>t;
for(int i=1; i<=t; ++i)
{
memset(a, 0, sizeof a);
memset(s, 0, sizeof s);
cout<<"Case "<<i<<":"<<endl;
int n;
cin>>n;
for(int i=1; i<=n; ++i) cin>>a[i];
int l = 1, r = 1, ls = 1;
int ans = -2e9, res = 0;
for(int i=1; i<=n; ++i)
{
res += a[i];
if(res > ans)
{
ans = res;
r = i;
ls = l;
}
if(res < 0)
{
res = 0;
l = i+1;
}
}
cout<<ans<<' '<<ls<<' '<<r<<endl;
if(i != t) cout<<endl;
}
return 0;
}
D - （最长上升子序列模板） HDU - 1087
//注意题目的数据范围，可能会爆int
# include<iostream>
# include<algorithm>
using namespace std;
const long long N = 1100;
long long n;
long long a[N];
long long dp[N]; //dp[i]是以第i个数字为结尾的最长上升子序列和
int main()
{
while(cin>>n, n)
{
for(long long i=1; i<=n; ++i) cin>>a[i];
for(long long i=1; i<=n; ++i) dp[i] = a[i];
//初始化，每个数都是一个子序列，每个格子的上升子序列的和都至少是自己
for(long long i=1; i<=n; ++i)
{
for(long long j=1; j<i; ++j)
{
if(a[j] < a[i]) dp[i] = max(dp[i], dp[j]+a[i]);
//如果j到i是上升子序列，那么取最值
}
}
//根据定义的dp数组的含义，求出最值
//注意：拥有最大和的上升子序列不一定是以原数组的最后一个数结尾，咱也不知道是以哪个数结尾，因此需遍历一遍整个数组，找出拥有最大和上升子序列
long long ans = -2e18;
for(long long i=1; i<=n; ++i) ans = max(ans, dp[i]);
cout<<ans<<endl;
}
return 0;
}
F - （最长上升子序列的优化） 计蒜客 - T2146
//对于拦截的每一个导弹，都有两种选择
//1. 使用之前的导弹拦截系统（前提是该导弹高度必须小于之前的导弹高度）
//2. 在开一个新的导弹拦截系统
# include<iostream>
# include<algorithm>
# include<cstring>
using namespace std;
const int N = 1e5+10;
int n;
int a[N];
int dp[N];
int f[N];
int main()
{
int cnt = 1;
while(cin>>a[cnt]) cnt++; // <cnt
cnt--;
//最长下降子（非上升）序列
memset(dp, 0x3f, sizeof dp);
for(int i=cnt; i; --i)
{
int x = a[i];
int j = upper_bound(dp, dp+cnt, x)-dp;
dp[j] = x;
}
int res = 0;
while(dp[res]!=0x3f3f3f3f) res++;
cout<<res<<endl;
//永远维护一个递增的序列
//贪心：能不创建新的导弹拦截系统就不创建新的导弹拦截系统
memset(f, 0x3f, sizeof f);
for(int i=1; i<=cnt; ++i)
{
int x = a[i];
int j = lower_bound(f, f+cnt, x)-f;
f[j] = x;
}
res = 0;
while(f[res]!=0x3f3f3f3f) res++;
cout<<res<<endl;
return 0;
}
G - （数字三角形的变形） 计蒜客 - T2153
# include<iostream>
# include<algorithm>
using namespace std;
const int N = 30;
int n;
int dp[N<<1][N][N]; //总坐标是i，a的横坐标是j，b的横坐标是k
int g[N][N];
int main()
{
cin>>n;
int a, b, c;
while(cin>>a>>b>>c, a||b||c) g[a][b] = c;
for(int i=2; i<=(n<<1); ++i)
{
for(int j=1; j<=n; ++j)
{
for(int k=1; k<=n; ++k)
{
if(j>=i || k>=i) continue;
if(j==k)
{
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k]+g[j][i-j]);
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1]+g[j][i-j]);
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]+g[j][i-j]);
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1]+g[j][i-j]);
}
else
{
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k]+g[j][i-j]+g[k][i-k]);
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1]+g[j][i-j]+g[k][i-k]);
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]+g[j][i-j]+g[k][i-k]);
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1]+g[j][i-j]+g[k][i-k]);
}
}
}
}
cout<<dp[n<<1][n][n]<<endl;
return 0;
}