kuangbin带你飞：点击进入新世界
文章目录
目录
1.Max Sum Plus Plus
原题链接：传送门
2.Ignatius and the Princess IV
原题链接：传送门
思路：hash存储（感觉和dp没啥关系啊。。）
#include<bits/stdc++.h>
using namespace std;
map<int, int>mp; int n, t;
int main() {
freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false); cin.tie(0);
while (cin >> n) {
mp.clear();
for (int i = 0; i < n; ++i) { cin >> t; mp[t]++; }
for (auto &p : mp) {
if (p.second >= (n + 1) / 2) { cout << p.first << endl; break; }
}
}
}
3.Monkey and Banana
原题链接：传送门
解析：对于所给的砖块可以有6种组合（即：长宽高打乱）所以最终的 $ index = 6 * n$
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000;
struct node {
int l, r, w;//长宽高
}a[maxn];
int n, r, w, l;
bool cmp(node &a, node &b) {
if (a.l == b.l)return a.r < b.r;
return a.l < b.l;
}
int dp[maxn];
int main() {
freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false); cin.tie(0);
int Case = 1;
while (cin >> n && n) {
int index = 1;
for (int i = 0; i < n; ++i) {
cin >> l >> r >> w;
a[index].l = l, a[index].r = r, a[index++].w = w;
a[index].l = r, a[index].r = l, a[index++].w = w;
a[index].l = w, a[index].r = r, a[index++].w = l;
a[index].l = l, a[index].r = w, a[index++].w = r;
a[index].l = r, a[index].r = w, a[index++].w = l;
a[index].l = w, a[index].r = l, a[index++].w = r;
}
sort(a + 1, a + index + 1,cmp);//根据长宽排序
memset(dp, 0,sizeof dp);
int ans = 0;
for(int i = 1;i <= index;++i)
for (int j = 1; j <= index; ++j) {
if (a[i].r < a[j].r && a[i].l < a[j].l)
dp[j] = max(dp[j], dp[i] + a[j].w), ans = max(ans, dp[j]);
}
cout << "Case " << Case++ << ": maximum height = " << ans << endl;
}
}
4.Doing Homework
解析：
先大致说说状态压缩，假设有三门作业a，b，c
那么，abc都做完即111，111可由101，110，011任意一个来得到。而101可以从100或者001来得到，这就是状态压缩dp的一个基本的状态转移。
#include<bits/stdc++.h>
using namespace std;
const int N = 16;
struct Node
{
char str[109];
int want, need;
}node[N];
struct DP
{
int now, sum, next, pos;
}dp[1 << N];
void put_ans(int x)
{
if (dp[x].next != -1)
{
put_ans(dp[x].next);
printf("%s
", node[dp[x].pos].str);
}
}
int main()
{
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s%d%d", node[i].str, &node[i].want, &node[i].need);
dp[0].now = dp[0].sum = 0;
dp[0].next = dp[0].pos = -1;
int m = (1 << n) - 1;
for (int i = 1; i <= m; i++)
{
dp[i].sum = 0x3f3f3f3f;
for (int j = 0; j < n; j++)
{
if ((1 << j) & i)
{
int k = i - (1 << j);
int v = dp[k].now + node[j].need - node[j].want;
v = max(v, 0);
if (dp[i].sum >= dp[k].sum + v)
{
dp[i].sum = dp[k].sum + v;
dp[i].now = dp[k].now + node[j].need;
dp[i].next = k;
dp[i].pos = j;
}
}
}
}
printf("%d
", dp[m].sum);
put_ans(m);
}
return 0;
}
5.Super Jumping! Jumping! Jumping!
解析：注意题目是严格上升子序列并不是连续上升子序列（导致我写错了转移方程2333）
#include<bits/stdc++.h>
using namespace std;
#define ms(a,b) (a,b,sizeof a)
const int maxn = 1e3 + 10;
int dp[maxn], a[maxn];
int n;
int main() {
freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false); cin.tie(0);
while (cin >> n && n) {
ms(dp, 0);
for (int i = 0; i < n; ++i)
cin >> a[i], dp[i] = a[i];
int ans = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if (a[j] > a[i])
dp[j] = max(dp[j], dp[i] + a[j]);
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
}
同样是LIS模板题：最少拦截系统：传送门
Piggy-Bank