로곡 P1021 우표 액면가 디자인

9678 단어 배낭.동적 기획낙곡

로곡 P1021 우표 액면가 디자인


그룹을 요구하는데 dfs로 검색하는 게 뻔한데 어떻게 판단할까요?
가방으로!!!
dp[i]는 i라는 수의 최소 우표 수를 모은 다음에 dp[i]<=n의 개수를 통계하면 된다
dfs에서 경계 문제가 하나 있다. 바로 다음 수를 선택할 때 그가 반드시 >=이전 수를 알고 있지만 그 위 경계는 분명하지 않다는 것을 알 수 있다.
그러나 몇 번의 시도를 통해 그 상계치는 반드시 <=현재 가장 큰 연속치임을 발견할 수 있다. 아무리 크면 현재 최대 연속치 +1의 빈자리가 생길 수 있기 때문이다.
위 코드:
#include 
using namespace std;
const int maxn=1e5+7;
int n,k,maxx;
int dp[maxn],a[maxn],ans[maxn];
int update(){
    int i=1;
    while(1){
        dp[i]=0x7fffffff;
        for(int j=1;j<=k && i-a[j]>=0;j++)
            dp[i]=min(dp[i],dp[i-a[j]]+1);
        if(dp[i] > n)
            break;
        i++;
    }
    i--;
    if(i>maxx){
        for(int j=1;j<=k;j++)
            ans[j]=a[j];
        return i;
    }
return maxx;
}
void dfs(int depth,int minn){
    if(depth>k){
        maxx=update();
        return;
    }
    for(int i=minn+1;i<=maxx+1;i++){//        
        a[depth]=i;
        dfs(depth+1,i);
    }
}
int main(){
    scanf("%d %d",&n,&k);
    maxx=n;
    a[1]=1;
    dfs(2,1);
    for(int i=1;i<=k;i++)
        printf("%d ",ans[i]);
    cout<<endl;
    printf("MAX=%d",maxx);
return 0;
}
API 및 Lambda 증폭
CSS 101 - 위치 정적 대 상대 대 절대 ​​위치

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage