글 읽기 - 왜 1차원 dp로 풀면 틀릴까요?

hsinh 4년 전 0

2차원 dp로 풀면 됩니다만 1차원으론 안되는 건가요?

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
ll d[1001], t[1001];
int main()
{
	ll n, k;
	cin>>n>>k;
	for(int i = 1; i <= n; i++)
	{
		ll a, ta, b, tb;
		cin>>ta>>a>>tb>>b;

		d[i] = d[i-1]; 
		t[i] = t[i-1];
		if(t[i-1] + ta <= k && t[i-1] + tb > k)
		{
			d[i] += a;
			t[i] += ta;
		}
		else if(t[i-1] + ta > k && t[i-1] + tb <= k)
		{
			d[i] += b;
			t[i] += tb;
		}
		else if(t[i-1] + ta <= k && t[i-1] + tb <= k)
		{
			if(a > b)
			{
				d[i] += a;
				t[i] += ta;
			}
			else if(b > a)
			{
				d[i] += b;
				t[i] += tb;
			}
			else
			{
				d[i] += a;
				t[i] += ta;
			}
		}
	}	
	cout<<d[n];
}

ecode 9달 전 0

1차원 DP로도 해결할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 1차원 dp로 풀면 틀릴까요?

hsinh 4년 전 0

ecode 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말