【NOIP2001】数的划分

本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1025

呃，我果然还是不行，连道水题都A不了。

整理了两种方法，都比较有代表性：搜索和DP。

搜索显然是穷举k位上每位都是什么数，为了避免重复，要控制使数的大小不下降；另外枚举时要加一个可行性剪枝，if(now+(k-d+1)*i>n) break。

 1 #include<cstdio>
 2 int n,k,ans;
 3 void dfs(int d,int now,int last) {
 4     if(d==k+1) {if(now==n) ++ans;return;}
 5     if(now>=n) return;
 6     for(int i=last;i<=n;++i) {
 7         if(now+(k-d+1)*i>n) break;
 8         dfs(d+1,now+i,i);
 9     }
10 }
11 int main() {
12     scanf("%d%d",&n,&k);
13     dfs(1,0,1);
14     printf("%d",ans);
15     return 0;
16 }

AC代码（搜索）

DP的话，主要是状态转移方程的推导（%dalao）。定义dp[i][j]表示使用j个数表示i的方案数，那么可以分类讨论，如果已选取的数中有1，那么dp[i][j]=dp[i-1][j-1]；如果没有1，dp[i][j]=dp[i-j][j]，相当于将选好的每个数减1（要求i>j，因为不能有0）。显然dp[i][1]=1，我们再将i从小到大枚举，就可以推出dp[n][k]。

 1 #include<cstdio>
 2 const int maxn=205,maxk=10;
 3 int n,k,dp[maxn][maxk];
 4 int main() {
 5     scanf("%d%d",&n,&k);
 6     for(int i=1;i<=n;++i) dp[i][1]=1;
 7     for(int j=2;j<=k;++j)
 8         for(int i=2;i<=n;++i) {
 9             if(i>j) dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
10             else dp[i][j]=dp[i-1][j-1];
11         }
12     printf("%d",dp[n][k]);
13     return 0;
14 }

AC代码