A.摘花生
题目描述
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1 ≤ T ≤ 100,
1 ≤ R,C ≤ 100,
0 ≤ M ≤ 1000
输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16
思路
状态表示：在第i行第j列最多摘到的花生数为f[i][j]
状态计算： f[i][j] = f[i][j] + max(f[i-1][j] , f[i][j-1])
C++ 代码
#include <bits stdc++.h>
#pragma GCC optimize(2)//O(2)优化
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
const int N = 110;
int f[N][N];
void solve()
{
int r , c;
cin >> r >> c;
for(int i = 1;i <= r;i ++) { for(int j="1;j" <="c;j" int x; cin>> x;
f[i][j] = x;
}
}
for(int i = 1;i <= r;i ++) { for(int j="1;j" <="c;j" f[i][j] +="max(f[i-1][j]," f[i][j-1]); } cout << "ans=";
cout << f[r][c] << endl;
}
int main()
{
/*读入优化*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while(T --)
solve();
return 0;
}
</code></pre><h2 id=" b合唱队形">B.合唱队形<h3 id="题目描述-1">题目描述</h3><p><code>N</code> 位同学站成一排，音乐老师要请其中的 <code>(N-K)</code> 位同学出列，使得剩下的 <code>K</code> 位同学排成合唱队形。</p><p>合唱队形是指这样的一种队形：设 <code>K</code> 位同学从左到右依次编号为 <code>1，2…，K</code>，他们的身高分别为 <code>T\_1，T\_2，…，T\_K</code>， 则他们的身高满足 <code>T\_1 < … < T\_i > T\_{i+1} > … > T\_K(1 ≤ i ≤ K)</code>。</p><p>你的任务是，已知所有 <code>N</code> 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。</p><h4 id="输入格式-1">输入格式</h4><p>输入的第一行是一个整数 <code>N</code>，表示同学的总数。</p><p>第二行有 <code>N</code> 个整数，用空格分隔，第 <code>i</code> 个整数 <code>T\_i</code> 是第 <code>i</code> 位同学的身高(厘米)。</p><h4 id="输出格式-1">输出格式</h4><p>输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。</p><h4 id="数据范围-1">数据范围</h4><p><code>2 ≤ N ≤ 100</code>,<br><code>130 ≤ T[i] ≤ 230</code></p><h4 id="输入样例-1">输入样例：</h4><pre><code>8
186 186 150 200 160 130 197 220
</code></pre><h4 id="输出样例-1">输出样例：</h4><pre><code>4
</code></pre><h3 id="思路-1">思路</h3><p><img src="https://img2022.cnblogs.com/blog/2731572/202208/2731572-20220809194314979-1586690309.png"><br><a href="https://www.acwing.com/solution/content/3805/" title="【转AcWing】yxc" rel="noopener">【转AcWing】yxc</a></p><h4 id="c-代码-1">C++ 代码</h4><pre><code>#include <bits stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
const int N = 110;
int n ;
int f[N] , g[N];
int h[N];
void solve()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin>> h[i];
for(int i = 1;i <= n;i ++) { f[i]="1;" for(int j="1;j" < i;j if(h[j] h[i]) , f[j] + 1); } i="n;i"> 0 ;i --)
{
g[i] = 1;
for(int j = n;j > i;j --)
{
if(h[j] < h[i])
g[i] = max(g[i] , g[j] + 1);
}
}
int res = 0;
for(int i = 1;i <= n;i ++) res="max(res,f[i]+g[i]-1);" cout << n-res endl; } int main() { *读入优化* ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); t; t="1;" cin>> T;
while(T --)
solve();
return 0;
}
</=></=></=></int,int></bits></code></pre><h2 id="c采药">C.采药</h2><h3 id="题目描述-2">题目描述</h3><p>辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。</p><p>为此，他想拜附近最有威望的医师为师。</p><p>医师为了判断他的资质，给他出了一个难题。</p><p>医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”</p><p>如果你是辰辰，你能完成这个任务吗？</p><h4 id="输入格式-2">输入格式</h4><p>输入文件的第一行有两个整数 <code>T</code> 和 <code>M</code>，用一个空格隔开，<code>T</code> 代表总共能够用来采药的时间，<code>M</code> 代表山洞里的草药的数目。</p><p>接下来的 <code>M</code> 行每行包括两个在 <code>1</code> 到 <code>100</code> 之间（包括 <code>1</code> 和 <code>100</code>）的整数，分别表示采摘某株草药的时间和这株草药的价值。</p><h4 id="输出格式-2">输出格式</h4><p>输出文件包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。</p><h4 id="数据范围-2">数据范围</h4><p><code>1 ≤ T ≤ 1000</code>,<br><code>1 ≤ M ≤ 100</code></p><h4 id="输入样例-2">输入样例：</h4><pre><code>70 3
71 100
69 1
1 2
</code></pre><h4 id="输出样例-2">输出样例：</h4><pre><code>3
</code></pre><h3 id="思路-2">思路</h3><p>与01背包问题一样，<br>区别：时间 --> 背包容量<br><strong>状态表示：所有只从前i个物品中选，且总时间不超过j的选法</strong><br><strong>状态计算：<code>f[i][j] = max(f[i][j] , f[i-1][j-v[i]]+w[i])</code></strong><br><img src="https://img2022.cnblogs.com/blog/2731572/202208/2731572-20220809175739705-808859243.png"></p><h4 id="c-代码-2">C++ 代码</h4><pre><code>#include <bits stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
const int N = 1010;
int n , m;
int t[N] , v[N];
int f[N][N];
void solve()
{
cin >> m >> n;
for(int i = 1;i <= n;i ++) cin>> t[i] >> v[i];
for(int i = 1;i <= n;i ++) { for(int j="0;j" <="m;j" f[i][j]="f[i-1][j];" if(j>= t[i])
f[i][j] = max(f[i][j] , f[i-1][j-t[i]]+v[i]);
}
}
cout << f[n][m] << endl;
}
int main()
{
/*读入优化*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
//cin >> T;
while(T --)
solve();
return 0;
}
</=></=></int,int></bits></code></pre><h2 id="d开心的金明">D.开心的金明</h2><h3 id="题目描述-3">题目描述</h3><p>金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。</p><p>更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 <code>N</code> 元钱就行”。</p><p>今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 <code>N</code> 元。</p><p>于是，他把每件物品规定了一个重要度，分为 <code>5</code> 等：用整数 <code>1 \\sim 5</code> 表示，第 <code>5</code> 等最重要。</p><p>他还从因特网上查到了每件物品的价格（都是整数元）。</p><p>他希望在不超过 <code>N</code> 元（可以等于 <code>N</code> 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。</p><p>设第 <code>j</code> 件物品的价格为 <code>v\[j\]</code>，重要度为 <code>w\[j\]</code>，共选中了 <code>k</code> 件物品，编号依次为 <code>j\_1，j\_2，…，j\_k</code>，则所求的总和为：</p><p><code>v\[j\_1\] \\times w\[j\_1\]+v\[j\_2\] \\times w\[j\_2\]+…+v\[j\_k\] \\times w\[j\_k\]</code></p><p>请你帮助金明设计一个满足要求的购物单。</p><h4 id="输入格式-3">输入格式</h4><p>输入文件的第 <code>1</code> 行，为两个正整数 <code>N</code> 和 <code>m</code>，用一个空格隔开。（其中 <code>N</code> 表示总钱数，<code>m</code> 为希望购买物品的个数）</p><p>从第 <code>2</code> 行到第 <code>m+1</code> 行，第 <code>j</code> 行给出了编号为 <code>j-1</code> 的物品的基本数据，每行有 <code>2</code> 个非负整数 <code>v</code> 和 <code>p</code>。（其中 <code>v</code> 表示该物品的价格，<code>p</code> 表示该物品的重要度）</p><h4 id="输出格式-3">输出格式</h4><p>输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 <code>10^8</code>）。</p><h4 id="数据范围-3">数据范围</h4><p><code>1 ≤ N < 30000</code>,<br><code>1 ≤ m < 25</code>,<br><code>0 ≤ v ≤ 10000</code>,<br><code>1 ≤ p ≤ 5</code></p><h4 id="输入样例-3">输入样例：</h4><pre><code>1000 5
800 2
400 5
300 5
400 3
200 2
</code></pre><h4 id="输出样例-3">输出样例：</h4><pre><code>3900
</code></pre><h3 id="思路-3">思路</h3><p>类似于01背包问题<br><strong>状态表示：从1到i中选，且总体积不超过j的所有选法的集合</strong><br><strong>状态计算：<code>f[i][j] = max(f[i][j] , f[i][j-v[i]]+w[i])</code></strong><br><img src="https://img2022.cnblogs.com/blog/2731572/202208/2731572-20220810172056720-1126700758.png"></p><h4 id="c-代码-3">C++ 代码</h4><pre><code>#include <bits stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
const int N = 35;
const int M = 30010;
int n , m;
int f[N][M];
void solve()
{
cin >> m >> n;
for(int i = 1;i <= n;i ++) { int v , w; cin>> v >> w;
w = v * w;
for(int j = 0;j <= m;j ++) { f[i][j]="f[i" - 1][j]; if(j>= v)
f[i][j] = max(f[i][j] , f[i-1][j-v]+w);
}
}
cout << f[n][m] << endl;
}
int main()
{
/*读入优化*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
//cin >> T;
T = 1;
while(T --)
solve();
return 0;
}
</=></=></int,int></bits></code></pre><h2 id="e空心菱形">E.空心菱形</h2><h3 id="题目藐视">题目藐视</h3><p>输入一个整数 n，输出一个空心菱形，其中每个边由 n 个'*'组成。</p><h4 id="输入格式-4">输入格式</h4><p>输入包含一个整数 n。</p><h4 id="输出格式-4">输出格式</h4><p>输出一个空心菱形，每个边由 n 个'*'组成 。</p><h4 id="数据范围-4">数据范围</h4><p><code>1≤n≤20</code>。</p><h4 id="思路-4">思路</h4><p>模拟（不知道dp思路）</p><h4 id="代码">代码</h4><pre><code>#include <bits stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
int n;
void solve()
{
cin >> n;
//上半部分
for(int i = 1;i <= n;i ++) { int k="n" - i; while(k --) printf(" "); if(i="=" 1) printf("*"); else * i 3; } printf("\n"); 下半部分 for(int 1;i>= 1;i --)
{
int k = n - i;
while(k --)
printf(" ");
if(i == 1)
printf("*");
else
{
printf("*");
int k = 2 * i - 3;
while(k --)
printf(" ");
printf("*");
}
printf("\n");
}
}
int main()
{
/*读入优化*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
//cin >> T;
T = 1;
while(T --)
solve();
return 0;
}
</=></int,int></bits></code></pre><h2 id="f大盗阿福">F.大盗阿福</h2><h3 id="题目描述-4">题目描述</h3><p>阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。</p><p>这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。</p><p>作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？</p><h4 id="输入格式-5">输入格式</h4><p>输入的第一行是一个整数 T (T≤50) ，表示一共有 T 组数据。</p><p>接下来的每组数据，第一行是一个整数 N(1≤N≤100,000)，表示一共有 N 家店铺。</p><p>第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000。</p><h4 id="输出格式-5">输出格式</h4><p>对于每组数据，输出一行。</p><p>该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。</p><h4 id="提示">提示</h4><p>对于第一组样例，阿福选择第 2 家店铺行窃，获得的现金数量为 8。对于第二组样例，阿福选择第 1 和 4 家店铺行窃，获得的现金数量为 10+14=24。</p><h4 id="样例输入">样例输入</h4><pre><code>2
3
1 8 2
4
10 7 6 14
</code></pre><h4 id="样例输出">样例输出</h4><pre><code>8
24
</code></pre><h3 id="思路-5">思路</h3><p><strong>状态表示：前i家店铺的最大金额<br>状态计算：<code>f[i] = max(f[i-1] , f[i-2]+a[i])</code></strong><br><img src="https://img2022.cnblogs.com/blog/2731572/202208/2731572-20220810172721695-1180875856.png"></p><h4 id="代码-1">代码</h4><pre><code>#include <bits stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
const int N = 100010;
int a[N] , f[N];
int n;
void solve()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin>> a[i];
for(int i = 1;i </=></int,int></bits></code></pre></=></=></int,int></bits>
Original: https://www.cnblogs.com/heystar/p/16566539.html
Author: HeyStar
Title: 【ACM】dp专场训练
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587908/
转载文章受原作者版权保护。转载请注明原作者出处！