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

제목: 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