poj3181[완전 가방+정수 분할]

2458 단어

제목: n을 세어 드릴게요. K를 세어 드릴게요. 이 n을 1-k의 수로 조합하면 몇 가지 조합 방식이 있는지 물어볼게요.사고방식: 가방의 무게는 n이다.그러면 1-k는 무거운 물건이고 가치는 수치이며 무게는 수치임을 알 수 있다.모든 무거운 물건은 무한으로 얻을 수 있으며, 문제는 완전 가방으로 바뀐다.우리가 dp[]로 방안 수를 대표하면 dp[0]=1;n=1000,k=1000일 때 이 방안의 수는 매우 크기 때문이다.다른 큰 소 블로그를 봤는데 이 정수 분할이 정말 좋네요.
하나는 높은 자리를 대표하고, 하나는 낮은 자리를 대표한다.

#include
#include
#include
#include
using namespace std;

typedef long long LL;
const LL INF=1e18;
const int N=1e3+10;
LL d1[N],d2[N];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));

    d2[0]=1;
    for(int i=1;i<=k;i++)
    {
        for(int j=i;j<=n;j++)
        {
            d1[j]=d1[j]+d1[j-i]+(d2[j]+d2[j-i])/INF;//  
            d2[j]=(d2[j]+d2[j-i])%INF;
        }
    }
    if(d1[n])
        printf("%lld",d1[n]);
    printf("%lld
",d2[n]);
    return 0;
}

전재 대상:https://www.cnblogs.com/keyboarder-zsq/p/5934894.html

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

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

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

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

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

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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