[폭력 검색] [동적 기획] [NOIP 1999] 우표 액면가 디자인

사실은 모든 우표의 액면가를 매거하여 엄격하게 증가하는 것을 기억하고 DP는 매번 최대 1-어느 액면가의 우표를 모을 수 있는지 판단한다. 그리고 하한선은 분명히 앞의 우표의 액면가 +1이다.상한선은 현재 모을 수 있는 우표의 액면가 +1이다. 왜냐하면 현재 최대가 n이라면 이 액면가가 n+2라면 n+1은 원래의 조합으로 구성될 수 없기 때문이다.DP에 관해서는 가방이니까 직접 밀어보세요.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXK 200
#define MAXN 50
#define MAXEND 10000
#define INF 0x7f7f7f7f
int K,N,F[MAXEND+10],Max;
vector<int> save;
vector<int> w;
int ret;
int dp(int E, int n){
    memset(F, INF, sizeof F); F[0] = 0;
    for(int V=1; V<=E; V++){
        for(int i=1; i<=n;i++){
            if(V - w[i] < 0) break;
            F[V] = min(F[V], F[V-w[i]] + 1);
        }
    }
    ret = 1;
    while(F[ret] <= K) ret++;
    return ret-1;
}
int length; 
void dfs(int u){
    if(u > N){
        length = dp(w[N]*K, u-1);
        if(length>Max){
            Max = length;
            save = w;
        }
        return ;
    }
    for(w[u]=dp(w[u-1]*K, u-1)+1;w[u]>w[u-1];w[u]--)
        dfs(u+1);
}
void solve(){
    w[1] = 1;
    dfs(2);
    printf("%d",save[1]);
    for(int i=2;i<=N;i++)
        printf(" %d",save[i]);
    printf("
MAX=%d
"
,Max); } int main() { scanf("%d %d",&K,&N); for(int i=0;i<=N;i++){ save.push_back(0); w.push_back(0); } solve(); return 0; }

좋은 웹페이지 즐겨찾기