P1115 最大子段和
题目描述
给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai。
输出格式
输出一行一个整数表示答案。
输入输出样例 #1
输入 #1
7
2 -4 3 -1 2 -4 3
输出 #1
4
说明/提示
样例 1 解释
选取 [3,5] 子段 {3,−1,2}，其和为 4。
数据规模与约定
- 对于 40% 的数据，保证 n≤2×103。
- 对于 100% 的数据，保证 1≤n≤2×105，−104≤ai≤104。
思路
在于一个区间i-j， 是否能取第j个
而每次f[i][j] 为当前a[i][j] 设置为起始(i,j)自己为一个区间
即f[i][j] = max(f[i][j], f[i][j - 1] + a[i][j])
从一维的角度上来理解
f[j] = a[j]
f[j] = max(f[j], f[j - 1] + a[j])
for(int i = 1; i <= n; i ++)
{
f[i] = a[i];
f[i] = max(f[i], f[i - 1] + a[i]);
}
LL res = -1e9;
for(int i = 1; i <= n; i ++) res = max(f[i], res);
cout << res;
P1802 5 倍经验日
题目背景
现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。
题目描述
现在 absi2011 拿出了 x 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。
由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 2 个药去打别人，别人却表明 3 个药才能打过，那么相当于你输了并且这两个属性药浪费了。
现在有 n 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。
要求求出最大经验 s，输出 5s。
输入格式
第一行两个数，n 和 x。
后面 n 行每行三个数，分别表示失败时获得的经验 losei，胜利时获得的经验 wini 和打过要至少使用的药数量 usei。
输出格式
一个整数，最多获得的经验的五倍。
输入输出样例 #1
输入 #1
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
输出 #1
1060
说明/提示
【Hint】
五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。
【数据范围】
- 对于 10% 的数据，保证 x=0。
- 对于 30% 的数据，保证 0≤n≤10，0≤x≤20。
- 对于 60% 的数据，保证 0≤n,x≤100， 10<losei,wini≤100，0≤usei≤5。
- 对于 100% 的数据，保证 0≤n,x≤103，0<losei≤wini≤106，0≤usei≤103。
这道题的dp状态表示为第i个位置上选择打败与不打败
如果有足够的空间在这个位置上有两种选择 判断哪种情况的经验值更高
f[j] = max(f[j] + l[i], f[j - v[i]] + w[i])
如果不行
f[j] = max(f[j], f[j] + l[j])
`for(int i = 1; i <= n; i ++)
{
for(int j = m; j >= 0; j --)
{
if(j >= v[i])
{
f[j] = max(f[j] + l[i], f[j - v[i]] + w[i]);
//cout << f[j] << " ";
}
else
{
f[j] = max(f[j], f[j] + l[i]);
}
}
}`
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
int f[N];
int cnt;
int find(int x)
{
int l = 1, r = cnt;
while(l < r)
{
int mid = (l + r) >> 1;
if(f[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
f[++ cnt] = a[1];
for(int i = 2; i <= n; i ++)
{
if(a[i] > f[cnt]) f[++cnt] = a[i];
else
{
a[i] 虽然不能让子序列变得更长，但它有可能替换掉 f 数组中某个已有的结尾元素，使得未来构成更长的上升子序列的可能性增加。具体来说，我们要找到 f 数组中第一个大于或等于 a[i] 的元素 f[t]，然后用 a[i] 替换掉它。
为什么这么做？因为 a[i] 比 f[t] 小（或相等），这意味着我们找到了一个长度为 t 的上升子序列，其结尾元素是 a[i]。这个新的长度为 t 的子序列比原来那个结尾为 f[t] 的子序列“更有潜力”，因为它结尾更小，更容易在后面接上其他元素。
int t = find(a[i]);
cout << t << " " << a[i] << endl;
f[t] = a[i];
}
}
//for(int i = 1; i <= n; i ++) cout << f[i] << " ";
cout << cnt;
}
计数类dp
f[i][j]总数和为i 数字选择个数为j
可分为两类 最小值数为1 和 最小值数大于1 即f[i - 1][j - 1] 和 f[i - j][j] 因为方案中去掉一个最小数为1 和 每个数减去1 不影响总方案数
so f[i][j] = f[i - j][j] + f[i - 1][j - 1]
int n;
cin >> n;
f[1][1] = 1;
for(int i = 2; i <= n; i ++)
{
for(int j = 1; j <= i;j ++)
{
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % M;
}
}
int res = 0;
for(int i = 1; i <= n; i ++) res = (res + f[n][i]) % M;
cout << res;
从完全背包问题的角度进行思考
第i个数选择与否 和选择后的个数
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] ... + f[i - 1][j - k * i]
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i]
so f[i][j] = f[i - 1][j] + f[i][j - 1]
方案数与最大值的不同 方案数在i为n j为0的情况下 让为一种方案的选择
cin >> n;
即总数容量为0的情况下 任意方案都不选也是一种方案
for(int i = 0; i <= n; i ++) f[i][0] = 1;
for(int i = 1; i <= n; i ++)
{
for(int j = 0; j <= n;j ++)
{
f[i][j] = (f[i - 1][j]) % M;
if(j >= i) f[i][j] = (f[i][j] + f[i][j - i]) % M;
}
}
cout << f[n][n];
优化为滚动数组
f[0] = 1;
for(int i = 1; i <= n; i ++)
{
for(int j = i; j <= n;j ++)
{
f[j] = (f[j] + f[j - i]) % M;
}
}
cout << f[n];
P1164 小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
题目描述
不过 uim 由于买了一些书，口袋里只剩 M 元 (M≤10000)。
餐馆虽低端，但是菜品种类不少，有 N 种 (N≤100)，第 i 种卖 ai 元 (ai≤1000)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 1 秒。
输入格式
第一行是两个数字，表示 N 和 M。
第二行起 N 个正数 ai（可以有相同的数字，每个数字均在 1000 以内）。
输出格式
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
输入输出样例 #1
输入 #1
4 4
1 1 2 2
输出 #1
3
01背包方案数问题
g[0] = 1;
for(int i = 1; i <= n;i ++)
{
for(int j = m; j >= v[i]; j --)
{
int val = f[j - v[i]] + w[i];
if(val > f[j])
{
f[j] = val;
g[j] = g[j - v[i]];
}
else if(val == f[j])
{
g[j] += g[j - v[i]];
}
}
}
//g[m]表示是在体积m的情况下 他的方案数
cout << g[m];
P1049 [NOIP 2001 普及组] 装箱问题
题目描述
有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。
现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。
输入格式
第一行共一个整数 V，表示箱子容量。
第二行共一个整数 n，表示物品总数。
接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。
输出格式
- 共一行一个整数，表示箱子最小剩余空间。
输入输出样例 #1
输入 #1
24
6
8
3
12
7
9
7
输出 #1
0
说明/提示
对于 100% 数据，满足 0<n≤30，1≤V≤20000。
通过令v = w 那么在消耗v的情况之下可得具体的消耗体积
故可得剩余空间体积 column = m - f[m]
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]);
}
}
//for(int i = 0; i <= m; i ++) cout << f[i] << " ";
//cout << g[2];
//int res = 0;
cout << m - f[m];
多重背包求解方案数 以及 具体方案
for(int i = 0; i <= m; i ++) g[0][i] = 1;
for(int i = 0; i <= n; i ++) g[i][0] = 1;
for(int i = 1; i <= n; i ++)
{
for(int j = 0; j <= m; j ++)
{
//g[i][j] = g[i - 1][j];
for(int k = 0; k * v[i] <= j && k <= s[i]; k ++)
{
//f[i][j] = f[i - 1][j];
int val = f[i - 1][j - k * v[i]] + k * w[i];
if(val > f[i][j])
{
f[i][j] = val;
g[i][j] = g[i - 1][j - k * v[i]];
}
else if(val == f[i][j])
{
g[i][j] += g[i - 1][j - k * v[i]];
}
}
}
}
//cout << g[n][m];
int current_cap = m;
int cnt = 0;
vector<pair<int, int>> temp;
for(int i = n; i >= 1; i --)
{
for(int k = s[i]; k >= 0; k --)
{
int remain_cap = current_cap - k * v[i];
int value = 0;
if(remain_cap >= 0)
{
value = f[i - 1][remain_cap] + k * w[i];
if(f[i][current_cap] == value)
{
if(k > 0) temp.push_back({i, k});
current_cap = remain_cap;
break;
}
}
}
}
if(!temp.empty())
{
for(auto i : temp)
{
int index = i.first;
int cnt = i.second;
//cout << index << " " << i.second << " " << v[index] <<endl;
cout << v[index] << " " << w[index] << cnt <<endl;
}
}
P1077 [NOIP 2012 普及组] 摆花
题目描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第 i 种花不能超过 ai 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入格式
第一行包含两个正整数 n 和 m，中间用一个空格隔开。
第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1,a2,⋯,an。
输出格式
一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 106+7 取模的结果。
输入输出样例 #1
输入 #1
2 4
3 2
输出 #1
2
说明/提示
【数据范围】
对于 20% 数据，有 0<n≤8,0<m≤8,0≤ai≤8。
对于 50% 数据，有 0<n≤20,0<m≤20,0≤ai≤20。
对于 100% 数据，有 0<n≤100,0<m≤100,0≤ai≤100。
NOIP 2012 普及组 第三题
多重背包方案数 计数问题 这里可以把v, w看成1
状态压缩
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
LL f[N][M]; // ??开到1 << M??
bool st[M]; //st[i] 为 true 当且仅当状态 i 所表示的那些需要被竖直骨牌填充的格子（对应 '0' 位）能够被完美填充。奇数个连续的空格是无法用 1x2 骨牌填满的。
vector<int> state[M];
int main()
{
int n, m;
while(cin >> n >> m, n | m) // ?? n | m -> 防止n, m 为0 进行多组数据测试
{
//设定st？
for(int i = 0; i < 1 << n; i ++)
{
int cnt = 0; // ??什么是cnt -> cnt用于记录1的个数
bool is_valid = true;
for(int j = 0; j < n; j ++)
{
//如果第i列伸出的第i+1列为1 检测cnt
if(i >> j & 1)
{
//这是干嘛的？？？ -> 如果cnt的个数为奇数 那么这个位置无法竖着放
if(cnt & 1)
{
is_valid = false;
break;
}
cnt = 0;
}
else cnt ++;
}
if(cnt & 1) is_valid = false;
st[i] = is_valid;
}
for(int i = 0; i < 1 << n; i ++)
{
state[i].clear();
for(int j = 0; j < 1 << n; j ++)
{
if((i & j) == 0 && st[i | j])
{
state[i].push_back(j);
}
}
}
memset(f, 0, sizeof(f));
f[0][0] = 1;
for(int i = 1; i <= m; i ++)
{
for(int j = 0; j < 1 << n; j ++)
{
for(auto k : state[j])
{
f[i][j] += f[i - 1][k];
}
}
}
cout << f[m][0] << endl;
}
}
看不懂
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int a[N][N];
int f[N][N];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int dp(int r, int c)
{
int &v = f[r][c];
if(v != -1) return v;
v = 1;
for(int i = 0; i < 4; i ++)
{
int x = r + dx[i], y = c + dy[i];
if(x >= 1 && x <= n && y >= 1 && y <= m && a[r][c] > a[x][y])
{
v = max(v, dp(x, y) + 1);
}
}
return v;
}
int main()
{
cin >> n >> m;
memset(f, -1 ,sizeof(f));
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> a[i][j];
int res = 0;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
res = max(res, dp(i, j));
}
}
cout << res;
return 0;
}
树形dp 感觉是有一定模板的 构造树那块得背一下
const int N = 6010;
int f[N][2];
int h[N], e[N], ne[N], idx;
int happy[N];
bool has_fa[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
f[u][1] = happy[u];
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][0] += max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> happy[i];
memset(h, - 1, sizeof(h));
for(int i = 0; i < n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(b, a);
has_fa[a] = true;
}
int root = 1;
while(has_fa[root]) root ++;
dfs(root);
cout << max(f[root][1], f[root][0]);
