[kuangbin 너를 데리고 날아간다] 주제 12 기초 DP1 문제풀이 + 요약
문서 목록
카탈로그
1.Max Sum Plus Plus
전송문
2.Ignatius and the Princess IV
전송문
사고방식:hash메모리(dp와 아무 상관이 없는 것 같은데...)
#include
using namespace std;
mapmp; 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
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(상태 압축 DP)
HDU - 1074
해결:
먼저 대체적으로 상태 압축을 말하고 세 개의 숙제가 a, b, c가 있다고 가정하면 abc가 모두 하면 11111111은 10110011 임의로 얻을 수 있다.101은 100이나 001에서 얻을 수 있는데 이것이 바로 상태 압축 dp의 기본적인 상태 이동이다.
#include
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!
HDU - 1087
해석: 주의 제목은 엄격한 상승자 서열이지 연속 상승자 서열이 아니다(내가 전이방정식 2333을 잘못 썼다)
#include
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 템플릿 문제: 최소 차단 시스템: 전송문
6.Piggy-Bank
HDU - 1114
동전마다 수량이 제한되지 않아 완전 가방입니다.dp수조를 초기화할 때 주의해야 한다. 가장 작고 제목이 적당히 채워진다는 뜻이기 때문에 dp수조는 INF로 초기화되었지만 dp[0]=0은 이때 용량이 0인 가방만 아무것도 넣지 않고 가치가 0인 상황에서'적당히 채워진다'는 뜻이다. 다른 용량의 가방은 모두 합법적인 해석이 없고 정의되지 않은 상태에 속한다(가방 9강)
#include
using namespace std;
const int N = 10010;
const int inf = 0x3f3f3f3f;
int dp[N], v[N], w[N];
int n, t, e, f;
int main() {
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> t; while (t--) {
cin >> e >> f;
int W = f - e;
cin >> n;
for (int i = 1; i <= n; ++i)cin >> v[i] >> w[i];
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = w[i]; j <= W; ++j)
dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
if(dp[W] == inf )printf("This is impossible.
");
else printf("The minimum amount of money in the piggy-bank is %d.
", dp[W]);
}
}
7. 무료 파이(수탑+역방향 DP)
HDU - 1176
아이디어:
만약에 시간축을 행수로 보고 각 점이 이 시간에 얻은 떡의 수를 열수로 본다면 a[i][j]는 시간이 i일 때 j점에서 얻은 떡을 나타낸다. 그림을 그려내면 이것은 사실 수탑문제라는 것을 알 수 있다.서로 인접한 양쪽을 처리해야 하기 때문에 0으로 표시할 때 처리하기 어려우므로 위치를 +1으로 한다.수탑 문제라면 뻔하다.
$ dp[i][j] = max({dp[i + 1][j - 1],dp[i + 1][j], dp[i + 1][j + 1]}) + a[i][j];$
이 문제를 좀 더 업그레이드하면 높이를 더한 것이다.POJ 1661Help Jimmy(역방향 DP Or 기억형 검색 Or 최단 경로)
#include
using namespace std;
#define ms(a,b) memset(a,b,sizeof a);
const int maxn = 1e5 + 50;
int t, x, y;
int a[maxn][15], dp[maxn][15];
int main() {
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while (cin >> t && t) {
ms(dp, 0);
ms(a, 0);
int e = 0;
for (int i = 0; i < t; ++i) { cin >> x >> y; a[y][++x]++; e = max(e, y); }
for (int i = e; i >= 0; i--)
for (int j = 1; j <= 11; j++)
dp[i][j] = max({dp[i + 1][j - 1],dp[i + 1][j], dp[i + 1][j + 1]}) + a[i][j];
cout << dp[0][6] << endl;
}
}
8.Tickets
HDU - 1260
아이디어:
#include
using namespace std;
const int maxn = 2010;
int a[maxn], b[maxn], dp[maxn];
int n, m, r, t = 0;
int main() {
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while (cin>>t) {
while (t--) {
cin >> n;
for (int i = 1; i <= n; ++i)cin >> a[i];
for (int i = 2; i <= n; ++i)cin >> b[i];
dp[1] = a[1];
for (int i = 2; i <= n; ++i)dp[i] = min(dp[i - 1] + a[i], dp[i - 2] + b[i]);
int h = 8, mi = 0, sec = 0;
sec += dp[n];
mi += sec / 60 % 60;
h += sec / 3600;
sec %= 60;
printf("%02d:%02d:%02d ", h, mi, sec);
if (h >= 12) printf("pm
");
else printf("am
");
}
}
}
9.FatMouse's Speed
HDU - 1160
#include
using namespace std;
struct Mouse
{
int id;
int speed;
int weight;
int pre;
int dp;
} mouse[10010];
int cmp(Mouse a, Mouse b)
{
if (a.weight == b.weight)
{
return a.speed > b.speed;
}
return a.weight < b.weight;
}
int dfs(int p)
{
//printf("@%d %d
",p,mouse[p].pre);
if (p == -1) return 0;
dfs(mouse[p].pre);
printf("%d
", mouse[p].id);
return 0;
}
int main()
{
int i = 0;
while (~scanf("%d%d", &mouse[i].weight, &mouse[i].speed))
{
mouse[i].id = i + 1;
mouse[i].pre = -1;
mouse[i].dp = 1;
i++;
}
sort(mouse, mouse + i, cmp);
int n = i;
mouse[0].dp = 1;
int ans = 1;
int p = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (mouse[i].weight > mouse[j].weight && mouse[i].speed < mouse[j].speed)
{
if (mouse[j].dp + 1 > mouse[i].dp)
{
mouse[i].dp = mouse[j].dp + 1;
mouse[i].pre = j;
}
}
}
if (mouse[i].dp > ans)
{
ans = mouse[i].dp;
p = i;
}
}
/*
for(int i=0;i 10.Jury Compromise
POJ - 1015
11.FatMouse and Cheese
HDU - 1078
아이디어:
#include
using namespace std;
const int maxn = 1e3 + 10;
int dp[maxn][maxn], a[maxn][maxn];
int nx[] = { 0,1,0,-1 };
int ny[] = { 1,0,-1,0 };
int n, m, r, t = 1;
int dfs(int x, int y) {
if (dp[x][y]) return dp[x][y];
int mx = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < 4; ++j) {
int xx = x + nx[j] * i, yy = y + ny[j] * i;
if (a[x][y] < a[xx][yy] && xx>0 && yy > 0 && xx <= n && yy <= n)
mx = max(dfs(xx, yy), mx);
}
}
return dp[x][y] = a[x][y] + mx;
}
int main() {
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while (cin >> n >> m && n != -1 &&m != -1) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
memset(dp, 0, sizeof dp);
cout << dfs(1, 1) << endl;
}
}
12.Phalanx
HDU - 2859
아이디어:
#include
using namespace std;
#define ms(a,b) memset(a,b,sizeof a);
const int N = 1010;
char a[N][N];
int dp[N][N];
int n;
int main() {
freopen("in.txt","r",stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while (cin >> n && n) {
ms(dp, 0);
int ans = 1;
for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
dp[i][j] = 1;
int x = i, y = j;
while (a[i][y] == a[x][j])x--, y++;
if(a[i][j + 1] == a[i - 1][j])
dp[i][j] = min(dp[i - 1][j + 1], i - x - 1) + 1;
ans = max(ans, dp[i][j]);
}
cout << ans << endl;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
