글 읽기 - 63퍼에서 틀립니다! 아무래도 접근이 틀린거같진 않은데 말이죠 ㅠㅠ

mic1021 6년 전 0

이 문제를 dp로 접근했습니다.

dp[i][c] = 현재 섭취한 칼로리가 c인 i번째 생물에 쌓이는 중금속량의 최솟값

for(i번째 생물의 먹이가 되는 생물들){
dp[i][c]= min(dp[i][c-E[j]] + dp[j][C[j]] , dp[i][c-E[k]] + dp[k][C[k]]) .....
}

위 점화식을 가지고 풀어봤는데 63퍼에서 틀렸다고 나오니까 반례가 있다는 건데..

'먹이를 먹을 때는 필요한 칼로리를 섭취하면서도 축적되는 중금속은 가장 적어지도록 먹이를 먹는다.' 라는 조건을 보면 제 접근방식이 맞다고 생각합니다..

혹시 반례가 있을런지요?

#include <cstdio>
#include <cstring>
#include <vector>
#define INF 1e9+7
#define min(a,b) (a)>(b)?(b):(a)
int dp[1001][10001],C[1001],H[1001],E[1001];
using namespace std;
vector <vector<int> > prey;
int memoi(int ord,int cal){
    if(C[ord]==0) return H[ord];
    if(cal<=0) return 0;
    int& ref=dp[ord][cal];
    if(ref!=-1) return ref;
    ref=INF;
    for(int i=0;i<prey[ord].size();++i){
        int prev=prey[ord][i];
        ref=min(ref,memoi(ord,cal-E[prev]) + memoi(prev,C[prev]));
    }
    return ref;
}
int main () {
    int n;scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&C[i],&H[i],&E[i]);
    }
    int m;scanf("%d",&m);
    prey.resize(n+1);
    for(int i=0;i<m;++i){
        int u,v;scanf("%d%d",&u,&v);
        prey[v].push_back(u);
    }
    int ans=memoi(n,C[n]);
    if(ans>H[n]) printf("no\n");
    else  printf("yes\n%d\n",ans);
    return 0;
}

mic1021 6년 전 0

한줄 추가하니까 맞았습니다 뜨네요 ㅂㄷㅂㄷ

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

문제

문제

출처

ICPC

63퍼에서 틀립니다! 아무래도 접근이 틀린거같진 않은데 말이죠 ㅠㅠ

mic1021 6년 전 0

mic1021 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말