赞
踩
如果你不太了解dp(动态规划)是个什么东西,请回到上次dp。
链接:动态规划算法详解
观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。
第一个行包含R(1≤ R≤1000),表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
单独的一行,包含那个可能得到的最大的和。
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
86
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 1005;
- int a[MAXN][MAXN], f[MAXN][MAXN], n;
- int main() {
- //读入
- cin >> n;
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= i; j++)
- {
- cin >> a[i][j];
- }
- }
- //初始化
- f[1][1] = a[1][1];
- //随时更新f[i][j]
- for(int i = 2; i <= n; i++) {
- for(int j = 1; j <= i; j++) {
- f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
- }
- }
- int ans = 0;
- //比较ans和f[n][i]
- for(int i = 1; i <= n; i++) {
- ans = max(ans, f[n][i]);
- }
- cout << ans << endl;
- return 0;
- }
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1001;
- int a[N], f[N], c[N];
- int main() {
- int n, maxx = -23333333;
- cin >> n;
- for (int i = 1; i <= n; i++) cin >> a[i];
- int k;
- for (int i = 1; i <= n; i++) {
- f[i] = 1;
- for (int j = 1; j < i; j++) {
- if (a[j] <= a[i] && f[j] + 1 > f[i])
- f[i] = f[j] + 1;
- }
- if (f[i] > maxx) {
- maxx = f[i];
- k = i;
- }
- }
- int q = 0, m = maxx, i = k - 1;
- c[q++] = k;
- while (m > 1) {
- if (f[i] == m - 1 && a[i] <= a[k]) {
- c[q++] = i;
- k = i;
- m--;
- }
- i--;
- }
- printf("max=%d", maxx);
- cout << endl;
- for (int i = q - 1; i >= 0; i--) printf("%d ", a[c[i]]);
- return 0;
- }
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。
为此,他想拜附近最有威望的医师为师。
医师为了判断他的资质,给他出了一个难题。
医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
输入格式
输入文件的第一行有两个整数 T和 M,用一个空格隔开,T代表总共能够用来采药的时间,M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间(包括 1 和 100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出文件包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
数据范围
1≤T≤1000,
1≤M≤100
输入样例:
- 70 3
- 71 100
- 69 1
- 1 2
输出样例:
3
- #include <bits/stdc++.h>
- using namespace std;
-
- int dp[10010];
- int money[101];
- int shijian[101];
- int t, shumu;
-
- int main()
- {
- scanf("%d%d", &t, &shumu);
- for(int i = 1; i <= shumu; i++)
- {
- scanf("%d%d", &shijian[i], &money[i]);
- }
- for(int i = 1; i <= shumu; i++)
- {
- for(int j = t; j >= shijian[i]; j--)
- {
- if(dp[j] < dp[j - shijian[i]] + money[i])
- {
- dp[j] = dp[j - shijian[i]] + money[i];
- }
- }
- }
- printf("%d", dp[t]);
- return 0;
- }
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。
阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。
他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
输入格式
输入的第一行是一个整数 T,表示一共有 T 组数据。
接下来的每组数据,第一行是一个整数 N ,表示一共有 N 家店铺。
第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据,输出一行。
该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
1≤T≤50
1≤N≤105
输入样例:
- 2
- 3
- 1 8 2
- 4
- 10 7 6 14
输出样例:
- 8
- 24
样例解释
对于第一组样例,阿福选择第2家店铺行窃,获得的现金数量为8。
对于第二组样例,阿福选择第1和4家店铺行窃,获得的现金数量为10+14=24。
- #include <bits/stdc++.h>
- using namespace std;
- #define read(a) scanf("%d", &a);
- const int N = 1e5 + 10, INF = 1e9;
- int t, n;
- int w[N], f[N][2];
- int main() {
- read(t);
- while(t--) {
- read(n);
- for(int i = 1; i <= n; i++) read(w[i]);
- f[0][0] = 0, f[0][1] = -INF;
- for(int i = 1; i <= n; i++) {
- f[i][0] = max(f[i - 1][0], f[i - 1][1]);
- f[i][1] = f[i - 1][0] + w[i];
- }
- printf("%d\n", max(f[n][1], f[n][0]));
- }
- return 0;
- }
在 n×n 的棋盘上放 k 个国王,国王可攻击相邻的 8 个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 n 和 k。
输出格式
共一行,表示方案总数,若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n2
输入样例:
3 2
输出样例:
16
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int N = 12, M = 1 << 10, K = 110;
- int n, m;
- vector<int> state;
- int cnt[M];
- vector<int> head[M];
- LL f[N][K][M];
- bool check(int state) {
- for (int i = 0; i < n; i++)
- if ((state >> i & 1) && (state >> i + 1 & 1))
- return false;
- return true;
- }
- int count(int state) {
- int res = 0;
- for (int i = 0; i < n; i++) res += state >> i & 1;
- return res;
- }
- int main() {
- cin >> n >> m;
- for (int i = 0; i < 1 << n; i++)
- if (check(i)) {
- state.push_back(i);
- cnt[i] = count(i);
- }
- for (int i = 0; i < state.size(); i++)
- for (int j = 0; j < state.size(); j++) {
- int a = state[i], b = state[j];
- if ((a & b) == 0 && check(a | b))
- head[i].push_back(j);
- }
- f[0][0][0] = 1;
- for (int i = 1; i <= n + 1; i++)
- for (int j = 0; j <= m; j++)
- for (int a = 0; a < state.size(); a++)
- for (int b : head[a]) {
- int c = cnt[state[a]];
- if (j >= c)
- f[i][j][a] += f[i - 1][j - c][b];
- }
- cout << f[n + 1][m][0] << endl;
- return 0;
- }
将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。
请编写一个程序,读入堆数 n 及每堆的石子数,并进行如下计算:
输入格式
第一行包含整数 n,表示共有 n 堆石子。
第二行包含 n 个整数,分别表示每堆石子的数量。
输出格式
输出共两行:
第一行为合并得分总和最小值,
第二行为合并得分总和最大值。
数据范围
1≤n≤200
输入样例:
- 4
- 4 5 9 4
输出样例:
- 43
- 54
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 410, INF = 0x3f3f3f3f;
- int n;
- int w[N], s[N];
- int f[N][N], g[N][N];
- int main() {
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> w[i];
- w[i + n] = w[i];
- }
- for (int i = 1; i <= n * 2; i++)
- s[i] = s[i - 1] + w[i];
- memset(f, 0x3f, sizeof f);
- memset(g, -0x3f, sizeof g);
- for (int len = 1; len <= n; len++)
- for (int l = 1; l + len - 1 <= n * 2; l++) {
- int r = l + len - 1;
- if (l == r)
- f[l][r] = g[l][r] = 0;
- else {
- for (int k = l; k < r; k++) {
- f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
- g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
- }
- }
- }
- int minv = INF, maxv = -INF;
- for (int i = 1; i <= n; i++) {
- minv = min(minv, f[i][i + n - 1]);
- maxv = max(maxv, g[i][i + n - 1]);
- }
- cout << minv << endl << maxv << endl;
- return 0;
- }
给定一棵树,树中包含 n 个结点(编号1~n)和 n−1 条无向边,每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说,要找到一条路径,使得使得路径两端的点的距离最远。
注意:路径中可以只包含一个点。
输入格式
第一行包含整数 n。
接下来 n−1 行,每行包含三个整数 ai,bi,ci,表示点 ai 和 bi 之间存在一条权值为 ci 的边。
输出格式
输出一个整数,表示树的最长路径的长度。
数据范围
1≤n≤10000
1≤ai,bi≤n,
−105≤ci≤
输入样例:
- 6
- 5 1 6
- 1 4 5
- 6 3 9
- 2 6 8
- 6 1 7
输出样例:
22
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 10010, M = N * 2;
- int n;
- int h[N], e[M], w[M], ne[M], idx;
- int ans;
- void add(int a, int b, int c) {
- e[idx] = b;
- w[idx] = c;
- ne[idx] = h[a];
- h[a] = idx++;
- }
- int dfs(int u, int father) {
- int dist = 0;//表示从当前点往下走的最大长度
- int d1 = 0, d2 = 0;
- for(int i = h[u]; i != -1; i = ne[i]) {
- int j = e[i];
- if(j == father) continue;
- int d = dfs(j, u) + w[i];
- dist = max(dist, d);
- if(d >= d1) d2 = d1, d1 = d;
- else if(d > d2) d2 = d;
- }
- ans = max(ans, d1 + d2);
- return dist;
- }
- int main() {
- cin >> n;
- memset(h, -1, sizeof h);
- for(int i = 0; i < n - 1; i++) {
- int a, b, c;
- cin >> a >> b >> c;
- add(a, b, c);
- add(b, a, c);
- }
- dfs(1, -1);
- cout << ans << endl;
- return 0;
- }
求给定区间 [X,Y] 中满足下列条件的整数个数:这个数恰好等于 K个互不相等的 B 的整数次幂之和。
例如,设 X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:
17=24+20
18=24+21
20=24+22
输入格式
第一行包含两个整数 X 和 Y,接下来两行包含整数 K 和 B。
输出格式
只包含一个整数,表示满足条件的数的个数。
数据范围
1≤X≤Y≤231−1,
1≤K≤20,
2≤B≤10
输入样例:
- 15 20
- 2
- 2
输出样例:
3
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 40;
- int K, B;
- int f[N][N];
- void init() {
- for(int i = 0; i < N; i++) {
- for(int j = 0; j <= i; j++)
- if(!j) f[i][j] = 1;
- else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
- }
- }
- int dp(int n) {
- if(!n) return 0;
- vector<int> nums;
- while(n) {
- nums.push_back(n % B);
- n /= B;
- }
- int res = 0, last = 0;
- for(int i = nums.size() - 1; i >= 0; i--) {
- int x = nums[i];
- if(x) {
- res += f[i][K - last];
- if(x > 1) {
- if(K - last - 1 >= 0) res += f[i][K - last - 1];
- break;
- }
- else {
- last++;
- if(last > K) break;
- }
- }
- if(!i && last == K) res++;
- }
- return res;
- }
- int main() {
- init();
- int l, r;
- cin >> l >> r >> K >> B;
- cout << dp(r) - dp(l - 1) << endl;
- }
输入一个长度为 n 的整数序列,从中找出一段长度不超过 m 的连续子序列,使得子序列中所有数的和最大。
注意: 子序列的长度至少是 11。
输入格式
第一行输入两个整数 n,m。
第二行输入 n 个数,代表长度为 n 的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数,代表该序列的最大子序和。
数据范围
1≤n,m≤300000,
保证所有输入和最终结果都在 int 范围内。
输入样例:
- 6 4
- 1 -3 5 1 -2 3
输出样例:
7
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 300010, INF = 1e9;
- int n, m;
- int s[N];
- int q[N];
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= n; i++) scanf("%d", &s[i]), s[i] += s[i - 1];
- int res = -INF;
- int hh = 0, tt = 0;
- for (int i = 1; i <= n; i++) {
- if (q[hh] < i - m) hh++;
- res = max(res, s[i] - s[q[hh]]);
- while (hh <= tt && s[q[tt]] >= s[i]) tt--;
- q[++tt] = i;
- }
- printf("%d\n", res);
- return 0;
- }
还有以下内容没有更新,敬请期待:
1.背包模型
2.状态机模型
3.状态压缩DP
4.区间DP
5.树形DP
6.数位DP
7.单调队列优化DP
8.斜率优化DP(因为我还没学,所以暂时不更新,请见谅)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。