这是我非常抗拒的一个算法点QAQ 因为真的很难 一直下意识地逃避不想学。

But最好面对恐惧的办法就是!疯狂刷题!!!

Yisin冲呀~

感谢awen给我们开的套题。特此鸣谢~

dp专题

A - Sum of Different Primes

题目传送门

以我拙劣的英语水平翻译一下是这样的:给你多组n和k,问用k个不同质数加和为n有多少种方案。

嘿咻!忽略掉质数和不重复两个关键词的话,这道题和《算法竞赛入门到进阶》(今年的一本新书,推荐,作者是华理的竞赛教练)dp入门的一题十分相似。

原题(hdu2069)如下:题目传送门

有n种硬币,面值分别为v1,v2,…,vn,数量无限。输入非负整数s,选用不多于100个硬币,使其和为s。输出所有可能的硬币组合。

那么我们可以定义一个矩阵元素dp[i][j],含义是用j个硬币实现金额i的数量方案。

  • 第一步:只用1分硬币实现

    初始dp[0][0]=1,其他为0。定义int type[5]={1,5,10,25,50}为5种硬币的面值。

    那么可以推导出来 dp[1][1] = dp[1][1] + dp[0][0] = dp[1][1] + dp[1-1][1-1] = 0 + 1 = 1

    dp[1-1][1-1]是因为从1分金额里减去1分硬币的钱,1个硬币的数量也减少了1个。

    所以这一步实际上是

    dp[1][1] = dp[1][1] + dp[1-type[0]][1-1]

  • 第二步:加上5分硬币,继续进行组合

    dp[i][j],当i<5时,组合里不可能有5分硬币。

    当i>=5时,金额为i,硬币为j个的组合数量等价于从i中减去五分钱,而且硬币数量也减去1个的情况。

    dp[i][j] = dp[i][j] + dp[i-5][j-1] = dp[i][j] + dp[i-type[1]][j-1]

  • 第三步:陆续加上10分、25分、50分硬币,同理有以下关系:

    dp[i][j] = dp[i][j] + dp[i-type[k]][j-1],k=2,3,4

所以代码就是

//#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

int type[5]={1,5,10,25,30};
int dp[251][101];
int n,k;

void solve()
{
    dp[0][0]=1;
    for(int i=0;i<5;i++)
    {
        for(int j=1;j<101;j++)
        {
            for(int k=type[i],k<251;k++)
            {
                dp[k][j]+=dp[k-type[i]][j-1];
            }
        }
    }
}

int main()
{
    int s;int ans[251]={0};
    solve();
    for(int i=0;i<251;i++)
    {
        for(int j=0;j<101;j++)
            ans[i]+=dp[i][j];
    }
    while(cin>>s)
        cout<<ans[s]<<endl;
    return 0;
}

明白了这道硬币题,那么这道题的思路也是一样的。只不过给定的数需要自己求。数据最大是1120,所以打个素数筛轻而易举,将1120前所有质数放进type数组里面。

所以一开始我是这么写的

//#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

int type[1005],ans=0;
ll dp[2005][20];
int n,k;

void init()
{
    for(int i=2;i<=1120;i++)
    {
        int flag=1;
        for(int j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                flag=0;
                break;
            }
        }
        if(flag)
            type[ans++]=i;
    }
}

void solve()
{
    dp[0][0]=1;
    for(int i=0;i<ans;i++)
    {
        for(int j=1;j<=k;j++)
        {
            for(int m=type[i];m<=n;m++)
            {
                dp[m][j]+=dp[m-type[i]][j-1];
            }
        }
    }
}

int main()
{
    init();
    while(scanf("%d %d",&n,&k)==2&&(n||k))
    {
        mem(dp,0);
        solve();
        cout<<dp[n][k]<<endl;
    }
    return 0;
}

然后我发现事情并不简单,因为这个程序连样例也并不能完全通过。于是我开始了漫长的debug之路,最后找到了问题所在!这个程序是有可能取重复素数的,因为取硬币的时候并没有要求每种类型只能取一个,但是这题规定了一个素数只能被加一次。

辣么,解决方案是什么呢?

让我们倒着来想。

dp[m][j]+=dp[m-type[i]][j-1]意味着:

type[i]dp[m-type[i]][j-1] 的计算中已经有可能被使用的情况下仍然继续被使用。

那么,如果我们换成dp[m+type[i]][j]+=dp[m][j-1],并让之前的加法倒转成一个减法呢?

也就是如下的循环:

for(int i=0;i<ans;i++)
    {
        for(int j=k;j>0;j--)
        {
            for(int m=n-type[i];m>=0;m--)
            {
                dp[m+type[i]][j]+=dp[m][j-1];
            }
        }
    }

一开始我也不太明白这个循环是怎么回事,后来观察了一下每一步的相加元素,就清楚了。一开始只有到dp[0][0]才能有值,所以只有dp[type[0]][1]才会有值。根据dp[type[0]][1],所以dp[type[0]+type[1]][2]也会有值;再根据dp[0][0],dp[type[1]][1]也会有值……就完成了每个元素的全排列。已经被用过的值是不可能再被使用的。妙啊!

所以这道题的最终程序是:

//#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

int type[1005],ans=0;
ll dp[2005][20];
int n,k;

void init()
{
    for(int i=2;i<=1120;i++)
    {
        int flag=1;
        for(int j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                flag=0;
                break;
            }
        }
        if(flag)
            type[ans++]=i;
    }
}

void solve()
{
    dp[0][0]=1;
    for(int i=0;i<ans;i++)
    {
        for(int j=k;j>0;j--)
        {
            for(int m=n-type[i];m>=0;m--)
            {
                dp[m+type[i]][j]+=dp[m][j-1];
            }
        }
    }
}

int main()
{
    init();
    while(scanf("%d %d",&n,&k)==2&&(n||k))
    {
        mem(dp,0);
        solve();
        cout<<dp[n][k]<<endl;
    }
    return 0;
}

小仙女