글 읽기 - 어떤 테스트 케이스에서 틀렸는지 잘 모르겠네요..

simjaemun2 7년 전 0

knuth optimization을 이용하여 DP를 구현하였는데,

어느 부분에서 틀렸는지 감을 못 잡겠습니다. ㅜㅜ

#define _CRT_SECURE_NO_WARNINGS 

#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

#define MAX_N 10000000
#define MAX_M 1000

typedef long long int LL;

int N, M;
int input[MAX_M + 10];
LL cache[MAX_M + 10][MAX_M + 10];
int K[MAX_M + 10][MAX_M + 10];

LL solve()
{
	LL INF = std::numeric_limits<LL>::max();

	for (int d = 2; d <= M + 1; d++)
	{
		for (int i = 0; i + d <= M + 1; i++)
		{
			int j = i + d;
			cache[i][j] = INF;

			for (int k = K[i][j - 1]; k <= K[i + 1][j]; k++)
			{
				LL v = input[j] - input[i] + cache[i][k] + cache[k][j];

				if (cache[i][j] > v)
				{
					cache[i][j] = v;
					K[i][j] = k;
				}
			}
		}
	}

	return cache[0][M + 1];
}

int main(int argc, char** argv)
{
	int tc, T;
	std::ios::sync_with_stdio(false);
#ifdef _WIN32
	freopen("Text.txt", "r", stdin);
#endif

	//cin >> T;
	T = 1;
	for (tc = 0; tc < T; tc++)
	{
		cin >> N >> M;

		for (int i = 1; i <= M; i++)
		{
			cin >> input[i];
			K[i - 1][i] = i;
		}
		K[M][M + 1] = M + 1;
		input[M + 1] = N;

		cout << solve() << endl;
	}

	return 0;
}

sgc109 7년 전 0

저도 맞는것같은데 틀리다고나오네요..ㅠㅠ 고수분들 저도 도와주세요..

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <set>
#include <cmath>
#include <deque>
// #include <unordered_set>
// #include <map>
#define REP(i,a,b) for(int i = a; i <= b;++i)
#define FOR(i,n) REP(i,0,n-1)
#define mp make_pair
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > vvi;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > piii;
typedef queue<int> QU;

const double EPSILON = 1e-9;
const double PI = acos(0.0)*2;
const int MOD = 1000000007;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;

ll D[1003][1003];
int K[1003][1003];
int N,M;
ll S[1003];
int A[1003];

int C(int l, int r){
	if(l>=r) return 0;
	return A[r]-A[l-1];
}
int main() {
	inp2(N,M);
	REP(i,1,M) inp1(A[i]);
	sort(A,A+M);
	A[++M]=N;
	memset(D,0x3c,sizeof(D));
	REP(i,1,M) D[i][i]=0,K[i][i]=i;
	for(int size=2;size<=M;size++){
		for(int i=1;i+size-1<=M;i++){
			int j=i+size-1;
			REP(k,K[i][j-1],K[i+1][j]){
				ll newV=D[i][k]+D[k+1][j]+C(i,j);
				if(D[i][j]>newV) D[i][j]=newV,K[i][j]=k;
			}
		}
	}
	printf("%lld",D[1][M]);
	return 0;
}

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

문제

문제

출처

ICPC

어떤 테스트 케이스에서 틀렸는지 잘 모르겠네요..

simjaemun2 7년 전 0

sgc109 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말