글 읽기 - 2419 사수아탕 반례 부탁드립니다.

dlftls38 4년 전 0

현 위치에서 왼쪽 바구니 사탕 위치로 갈지, 오른쪽 바구니 사탕 위치로갈지 DP로 풀어보았습니다.

제가 생각해본 예제 약 20개로는 맞는 코드와 비교했을 때 모두 같게 나오는데도 제출해보면 틀렸다고나오네요.

n이 0일 때

n이 1일 때

위치 0 에 사탕 바구니가 있을 때

한쪽 방향에만 있을 때

양쪽방향 모두 있을 때 등등...해보았습니다.

혹시 반례가 있으시다면 부탁드립니다.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <limits.h>
#include <functional>
#include <math.h>
#include <fstream>
#define INF 987654321
#define MAX_VALUE 1000000000
#define MOD 1000000009
#define pi 3.141592
using namespace std;
typedef pair<int,int> pii;
int n,m,ans;
vector<int>v;
int dp[333][333][333];
map<int,int>mp;
int solve(int cur, int time, int l, int r){
	//printf("%d %d %d %d\n",cur,time,l,r);
	int &ret = dp[mp[cur]][l][r];
	//printf("%d %d %d %d %d\n",cur,time,l,r,ret);
	if(ret!=-1){
		//printf("?\n");
		return ret;
	}
	ret=0;
	//printf("%d %d %d %d %d !\n",cur,time,l,r,ret);
	if(l>=1){
		//printf("1\n");
		int a = solve(v[l],time+abs(cur-v[l]),l-1,r);
		int b = max(0,m-(time+abs(cur-v[l])));
		//printf("%d + %d = %d // %d\n",a,b,a+b,ret);
		ret = max(a+b,ret);
		//ret=max(solve(v[l],time+abs(cur-v[l]),l-1,r)+max(0,m-(time+abs(cur-v[l]))),ret);
	}
	if(r<=n){
		//printf("2\n");
		int a = solve(v[r],time+abs(cur-v[r]),l,r+1);
		int b = max(0,m-(time+abs(cur-v[r])));
		//printf("%d + %d = %d // %d\n",a,b,a+b,ret);
		ret = max(a+b,ret);
		//ret=max(solve(v[r],time+abs(cur-v[r]),l,r+1)+max(0,m-(time+abs(cur-v[r]))),ret);
	}
	//printf("%d %d %d %d %d ?\n",cur,time,l,r,ret);
	return ret;
}
int main(){
	cin>>n>>m;
	if(n==0){
		printf("0");
		return 0;
	}
	int i,j;
	int check=0;
	for(i=0;i<n;i++){
		int x;
		cin>>x;
		if(n==1){
			printf("%d",max(0,m-abs(x)));
			return 0;
		}
		if(x==0){
			check=m;
		}
		else{
			v.push_back(x);
		}
	}
	if(check!=0){
		n--;
	}
	v.push_back(-INF);
	sort(v.begin(),v.end());
	for(i=1;i<=n;i++){
		mp[v[i]]=i;
	}
	mp[0]=0;
	int l=0;
	int r=n+1;
	for(i=1;i<=n;i++){
		if(v[i]<0){
			l=i;
		}
		else{
			break;
		}
	}
	for(i=n;i>=1;i--){
		if(v[i]>0){
			r=i;
		}
		else{
			break;
		}
	}
	for(i=0;i<333;i++){
		for(j=0;j<333;j++){
			for(int k=0;k<333;k++){
				dp[k][i][j]=-1;
			}
		}
	}
	printf("%d",solve(0,0,l,r)+check);
}

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

문제

문제

출처

ICPC

2419 사수아탕 반례 부탁드립니다.

dlftls38 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말