admin 管理员组

文章数量: 887021

题目


一、首先考虑一下基本情况：

查克拉分身
0n
1n
n1

该三种情况下始终只有一种情况，即K=1。

二、 当查克拉能量数量小于分身数量时

易知x个查克拉能量，最多给x个分身分配能量，多余的分身都只能为0查克拉能量。
所以多出来的分身无论有多少都不会影响分配情况K的大小。即当查克拉能量小于分身数量时，K的大小始终和查克拉等于分身数量时的K的大小。

三、建立一个二维数组dp[11][11]
dp[ x ][ y ]代表在 x 个查克拉能量和 y 个分身时的分配情况K的数目。
此时结合上面讲的第二点，可得该代码

if(x<y)
{dp[x][y]=dp[x][x];
}

四、当查克拉能量大于分身数量时（x个查克拉能量，y个分身）
该情况我们可以分为两种情况来看
1、有一个分身始终为0不分配能量
2、全部分身必须有能量
这两种情况加起来就是全部情况。

先看第一种情况，因为有一个分身不分配，所以该情况就可以转换为x个查克拉能量，y-1个分身时分配方式数量。再结合数组，此时的K就是dp[ x ][ y-1 ];

再看第二种情况，因为该情况下的分身必须都有能量，所以有y个查克拉能量固定分配，一个分身一个，我们不能动。此时我们的能量就剩下了x-y个查克拉能量，所以该情况就可以转换为x-y个查克拉分配给y个分身时的分配方式数量。结合数组，此时的K就是dp[ x-y ][ y ]

综上，当查克拉能量大于分身数量时，K为dp[ x ][ y-1 ]+dp[ x-y ][ y ]
所以有如下代码

if(x>y)
{dp[x][y]=dp[x][y-1]+dp[x-y][y];
}

五、题解代码
这题我们可以先求出0-10个查克拉分给0-10个分身时的所有K，然后再根据输入的M，N给出对应数据。

#include<iostream>using namespace std;int main()
{int dp[11][11];for(int i=1;i<11;i++)//对应第一步的基本情况初始化，其他情况的K均由这些基本情况推出{dp[0][i]=dp[1][i]=dp[i][1]=1;}for(int x=2;x<11;x++)//遍历剩下的情况，开始求K{for(int y=2;y<11;y++){if(x<y)//对应第二部分，查克拉小于分身{dp[x][y]=dp[x][x];}else//查克拉大于等于分身{dp[x][y]=dp[x][y-1]+dp[x-y][y];}}}int t;cin>>t;while(t--)//t个测试数据{int M,N;cin>>M>>N;cout<<dp[M][N]<<endl;//输出对应数目即可}return 0;
}

本文标签： 题目

版权声明：本文标题：题目 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687923090h157912.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。