题目链接
https://ac.nowcoder.com/acm/contest/9715/C
解题思路
找关系：
总共m个重音符，除去最左边的重音符还剩m-1个，我们确定最左边重音符的位置，计算此时剩下的m-1个重音符的位置关系有多少种：
- 假设m-1=1，
最左边的重音符偏移了0位，即如下图：此时，m-1个重音符的位置只能如图所示，即1种；
最左边的重音符偏移了1位，即如下图：此时，m-1个重音符可以在标准位置不变也可以向前偏移一个位置，即蓝色圆形，即2种；
最左边的重音符偏移了2位，即如下图：此时，m-1个重音符可以在标准位置不变也可以向前偏移一个位置，还可以偏移三个位置，即蓝色圆形，即3种； - 假设m-1=2，
就有
最左边的重音符偏移了0位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0；
最左边的重音符偏移了1位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，或者1，0，或者1，1；
最左边的重音符偏移了2位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，或者1，0，或者1，1，或者2，0，或者2，1，或者2，2；
最左边的重音符偏移了3位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，或者1，0，或者1，1，或者2，0，或者2，1，或者2，2，或者3，0，或者3，1，或者3，2，或者3，3；
…… - 假设m-1=3，
就有
最左边的重音符偏移了0位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，0；
最左边的重音符偏移了1位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，0，或者1，0，0，或者1，1，0，或者1，1，1；
最左边的重音符偏移了2位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，0，或者1，0，0，或者1，1，0，或者1，1，1，或者2，0，0，或者2，1，0，或者2，1，1，或者2，2，0，或者2，2，1，或者2，2，2；
……
这样一来我们可以列个表：
找到规律：
每个位置的值都等于它上一个和左一个的和，所以转移方程为 dp[i][j]=dp[i-1][j]+dp[i][j-1]
初始化：
dp[0][i]=1;
AC代码
const int N=1005;
const int MOD=1000000007;
int dp[N][N],ans;
class Solution {
public:
/**
*
* @param n int整型 乐谱总音符数
* @param m int整型 重音符数
* @param k int整型 重音符之间至少的间隔
* @return long长整型
*/
long long solve_bangbang(int n, int m, int k) {
// write code here
if(m==0) return 1;//！！！没有重音符的时候是1种情况
for(int i=1;i<=n-(m-1)*(k+1);i++) dp[0][i]=1;//最大偏移量为n-(m-1)*(k+1)-1，i=1表示偏移量为0的情况
for(int i=1;i<=m-1;i++)
for(int j=1;j<=n-(m-1)*(k+1);j++)
//for(int k=1;k<=j;k++)//<=> dp[i][j-1]
//dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
for(int i=1;i<=n-(m-1)*(k+1);i++)//累加一下就是答案
ans=(ans+dp[m-1][i])%MOD;
return ans;
}
};个人总结
我裂开，居然找错转移方程了，而且找错误的转移方程也找了巨久……我是FW……
京公网安备 11010502036488号