luogu 문제 풀이 P1510 [정 위 매 립 해]

간단 하기 그 지 없 는 01 배낭 물 문제, 하지만 내 수준 으로 는 물 문제 만 낼 수 있 겠 지 QAQ.
이것 은 01 가방 의 판자 가 아니 라 변형 을 넣 었 어야 하기 때문에 작은 구덩이 가 있 을 수 있 지만 새로운 학자 에 게 는 좋 은 연습 문제 일 것 이다.
우선, 우 리 는 먼저 내부 변 수 를 주의해 야 한다.

int vn,n,c,sum;//vn：need—v（     ） n：     c：    
int v[MAXN],w[MAXN],f[MAXN];//v：     w：

그 다음 에 데이터 범위 < = 10000 이 조금 크기 때문에 읽 기 최적화 (출력 이 적기 때문에 출력 하지 않 아 도 QAQ 최적화)

inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch'9') {if(ch=='-')f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0'; ch=getchar();}
    return x*f;
}

앞의 준비 작업 을 다 한 후에 기분 좋게 물 문 제 를 시작 할 수 있 습 니 다.
01 가방 이 변형 되 었 기 때문에 그 상태 전이 방정식 을 먼저 생각해 야 한다.
본인 의 생각 은 체력 을 가방 으로 보고 돌 을 물건 으로 보고 자 연 스 럽 게 본 문제 의 상태 전이 방정식 을 얻 었 습 니 다.

f[j]=max(f[j],f[j-w[i]]+v[i])

그 다음 에 33951 의 코드 입 니 다.

#include
#include
#include
#include
#define int long long
#define MAXN 10000+3
using namespace std;

inline int read(){//（    ）                          QAQ 
    int x=0,f=1;char ch=getchar();
    while (ch'9') {if(ch=='-')f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0'; ch=getchar();}
    return x*f;
}

int vn,n,c,sum;//vn：need—v（     ） n：     c：    
int v[MAXN],w[MAXN],f[MAXN];//v：     w：      

signed main()
{
    vn=read(),n=read(),c=read();
    for(int i=1;i<=n;i++){
        v[i]=read(),w[i]=read();
//      cout<=w[i];j--){
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
    for(int i=0;i<=vn;i++){//           vn     
        if(f[i]>=vn){
            cout<

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

luogu 문제 풀이 P1510 [정 위 매 립 해]

간단 하기 그 지 없 는 01 배낭 물 문제, 하지만 내 수준 으로 는 물 문제 만 낼 수 있 겠 지 QAQ. 이것 은 01 가방 의 판자 가 아니 라 변형 을 넣 었 어야 하기 때문에 작은 구덩이 가 있 을 수 있...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

luogu 문제 풀이 P1510 [정 위 매 립 해]

좋은 웹페이지 즐겨찾기