1304:数的划分

数的划分

鸣人的影分身 不能说相似吧,只能说一模一样。

深搜应该也没问题,这里就不尝试了。

下面贴一个dp解法(上一题的注释懒得改了⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄)

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=205;
 5 int f[8][N][N];
 6 
 7 int main(){
 8     int m,n;
 9     cin>>m>>n;
10     //初始化
11     // memset(f,0,sizeof(f));
12     for(int i=0;i<=m;i++)f[1][i][i]=1;
13     //f[i][j][k]表示第i个人分配j查克拉,前i个人共分配k查克拉
14     for(int i=2;i<=n;i++){
15         for(int j=1;j<=m;j++){
16             for(int k=j;k<=m;k++){
17                 for(int l=j;l>0;l--){//第i-1个人分配多少查克拉
18                     f[i][j][k]+=f[i-1][l][k-j];
19                 }
20             }
21         }
22     }
23     int ans=0;
24     for(int i=m/n;i<=m;i++)
25         ans+=f[n][i][m];
26     cout<<ans<<endl;
27     return 0;
28 }

 

上一篇:7305. 【2021.10.16NOIP提高组模拟】厜蓧篈壻鑨


下一篇:动态规划-最长连续递增序列