例1 P1832 A+B Problem（再升级）

胡乱分析

看着像是要搜索但是我感觉搜索应该得tle，这个就是比较朴素的取数问题变形了
首先我们定义v是背包容量,n是[2,n]内有多少个质数这样把质数放进背包的板子就成型了
注意初始值设定dp[0]=1表示什么都不装是有1个的(即这个数本身也算一种)

代码

#include <bits/stdc++.h>
using namespace std;
int isp(int n)
{
  for(int i=2;i*i<=n;i++)
  if(n%i==0)
  return 0;
  return 1;
}
long long dp[6666],bk[6666],mk[6666],v[6666],p=1;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,sum=0;
  dp[0]=1;
  for(int i=2;i<=1000;i++)
  if(isp(i))
  bk[i]=1;
  for(int i=2;i<=1000;i++)
  {
    if(bk[i])
    {
      v[p++]=i;
      sum++;
    }
    mk[i]=sum;
  }
  cin>>n;
  for(int i=1;i<=mk[n];i++)
  for(int j=v[i];j<=n;j++)
  dp[j]+=dp[j-v[i]];
  cout<<dp[n];
}

例2 P1679 神奇的四次方数

胡乱分析

跟例一一模一样注意这里就是把素数换成了四方数把方案数换成了最少的个数同样套板子即可
v是这个数的大小，n是[1,n]内有几个四方数
这里dp[0]=0数本身不算分解的一部分

代码

#include <bits/stdc++.h>
using namespace std;
double num[66666],mk[666666];
int sum,p=1,dp[666666];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset(dp,0x7f,sizeof(dp));
  dp[0]=0;
  for(double i=1;;i++)
  if(pow(i,4)<=1e5)
  num[p++]=pow(i,4);
  else
  break;
  p=1;
  for(int i=1;i<=int(1e5);i++)
  {
    if(i==num[p])
    {
      p++;
      sum++;
    }
    mk[i]=sum;
  }
  int n;
  cin>>n;
  for(int i=1;i<=mk[n];i++)
  for(int j=num[i];j<=n;j++)
  dp[j]=min(dp[j],dp[int(j-num[i])]+1);
  cout<<dp[n];
}

例3 自然数无序拆分

题目描述(摘自中石油oj 10255)

美羊羊给喜羊羊和沸羊羊出了一道难题，说谁能先做出来，我就奖励给他我自己做的一样礼物。沸羊羊这下可乐了，于是马上答应立刻做出来，喜羊羊见状，当然也不甘示弱，向沸羊羊发起了挑战。
可是这道题目有一些难度，喜羊羊做了一会儿，见沸羊羊也十分头疼，于是就来请教你。
题目是这样的：
把自然数Ｎ（N<＝100）分解为若干个自然数之和，求出有几种情况。
如N＝5时，有7种情况
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
5=5
怎么样？你要加油帮助喜羊羊哦！

胡乱分析

还是典型的问题，这个更简单了。。。实际上就是套板子即可v是n个数n是n个数
注意dp[0]=1代表数本身是算一个的

代码

#include <bits/stdc++.h>
using namespace std;
int dp[666];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  dp[0]=1;
  for(int i=1;i<=n;i++)
  for(int j=i;j<=n;j++)
  dp[j]+=dp[j-i];
  cout<<dp[n];
}