8615 快乐
Description
做出第i道题后，快乐指数将增加gethappy[i],消耗掉的精力将是losspow[i]
初始的快乐指数为1，精力为2000
最终剩余的精力必须大于0
计算得到的最多的快乐指数
输入格式
第一行输入一个整数n，表示有n道题。(n<=50)
第二行输入n个整数，表示gethappy[1]到gethappy[n]
第三行输入n个整数，表示losspow[1]到losspow[n]。
输出格式
一个整数，表示Lian所能获得的最大快乐指数。
输入样例
3
15 23 61
350 1301 1513
输出样例
77
01背包问题
只需注意两个细节：
（1）初始快乐指数为1
（2）剩余精力大于0
#include <iostream>
#include <cmath>
#include<algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2500;
int v[N]; // 精力
int w[N]; // 快乐
int f[N][N]; // f[i][j], j精力下前i题的最大快乐指数
int main()
{
int n, m;
cin >> n;
m = 2000;
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++)
//保证最后的精力1
for (int j = 1; j <= m - 1; j++)
{
// 当前精力做不了下一题，则快乐等于前i-1题
f[i][j] = f[i - 1][j];
// 能做，需进行决策是否选择要做
if (j >= v[i])b
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
//初始快乐为1，所以加1
cout << f[n][m - 1] + 1 << endl;
return 0;
}
一维优化
#include <iostream>
#include <cmath>
#include<algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2500;
int v[N]; // 精力
int w[N]; // 快乐
int f[N]; // f[j], j精力下的最大快乐指数
int main()
{
int n, m;
cin >> n;
m = 2000;
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++)
for (int j = m-1; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m - 1] + 1 << endl;
return 0;
}
18705 01背包问题
Description
有一个容积为M的背包和N件物品。第i件物品的体积W[i]，价值是C[i]。求解将哪些物品装入背包可使价值总和最大。每种物品只有一件，
可以选择放或者不放入背包。
输入格式
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；
第2…N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。
输出格式
一个数，表示最大总价值。
输入样例
10 4
2 1
3 3
4 5
7 9
输出样例
12
01背包
即对某一物品最多选取一次
状态表示：
f(i)(j), j体积下前i个物品的最大价值
状态转移方程：
f[i][j] = f[i - 1][j];
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
#include <iostream>
#include<cstring>
using namespace std;
const int MAXN = 1500;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int f[MAXN][MAXN]; // f[i][j], j体积下前i个物品的最大价值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
// 当前背包容量装不进第i个物品，则价值等于前i-1个物品
f[i][j] = f[i - 1][j];
// 能装，需进行决策是否选择第i个物品
if(j>=v[i])
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
一维优化
#include <iostream>
#include <cmath>
#include<algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1005;
int f[N];//j体积的最大价值
int v[N];//体积
int w[N];//价值
int n,m;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> m >> n;
for (int i = 1; i <=n ; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j -- ) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
18308 最长公共子序列
Description
给定两个字符串，请输出这两个字符串的最大公共子序列
输入格式
两行，一行一个字符串（不包括空格，Tab键）,长度不超过1000
输出格式
输出最大公共子序列的长度
输入样例
abbca
aba
输出样例
3
状态表示：
f [i] [j]：表示字符串a的前i个字符和字符串b的前j个字符之间的最长公共子序列的长度
#include <iostream>
#include<cstring>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int main() {
cin >> a+1 >> b +1;
int n = strlen(a+1), m = strlen(b+1);
// cout << n << m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j])
f[i][j] = f[i - 1][j - 1] + 1;
else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
cout << f[n][m] << '\n';
return 0;
}
8596 最长上升子序列
Description
当元素 ai1 < ai2 < … < aiK. 就说这个序列是有序上升的。
给定序列(a1, a2, …, aN)，存在许多这样的子序列(ai1, ai2, …, aiK)，
其中1 <= i1 < i2 < … < iK <= N.
也就是说，子序列是原序列允许挑选若干不连续的元素形成的序列。
举个例子，序列 (1, 7, 3, 5, 9, 4, 8) 就有许多个上上子序列，比如(1, 7), (3, 4, 8) 等。
所有这些上升子序列中最长的长度为4，比如 (1, 3, 5, 8).
你来编程实现，当给定一个初始序列，寻找这个序列的最长上升子序列。
输入格式
此例包含多个测试cases（少于100组test cases）。
每一组test case包含2行。
第一行是这组case的序列长度 N。（N的范围0~10000）
第二行包含 N个整数的一个序列，用空格间隔这N个整数， 1 <= N <= 10000。
当N为0时，表示测试结束。
输出格式
输出必须对每个test case，都有一个整数结果，表示这组case的最长上升子序列的长度。
输入样例
7
1 7 3 5 9 4 8
6
1 8 3 6 5 9
5
1 2 3 4 5
0
输出样例
4
4
5
#include <iostream>
#include <algorithm>
#include <queue>
#include<string>
using namespace std;
const int N = 10100;
int n;
int a[N];//数组a存序列
int f[N];//f[i]表示：直到第i个元素的最大上升子序列
int main()
{
while (cin>>n && n) {
for (int i = 0; i < n; i++) {
cin >> a[i];
f[i] = 1;
}//初始化为1，表示最少有1个上升子序列
//j在前，i在后，用前来更新后
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
//状态转移
if (a[j] < a[i]) f[i] = max(f[j] + 1, f[i]);
int ans = 0;
for (int i = 0; i < n; i++)ans = max(ans, f[i]);
cout << ans << endl;
}
return 0;
}
