这道题有两种解法:
1.DP解法
2.记忆化搜索
DP思路
其实可以把全部的设为一条线m,我们把m给切割成若干段。m[i]表示到i为止的方案总数。
其实这道题很像单词的划分 http://code.qingtengbc.com/problem/10250 的
上AC代码!!!!!!!!!!!!
#include<bits/stdc++.h>
using namespace std;
int n,m,f[1010][1010],a[10010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<=n;i++) f[0][i]=1;
for(int i=1;i<=m;i++){
for(int k=1;k<=n;k++){
for(int j=0;j<=i;j++){
if(i-j<=a[k]) f[i][k]=(f[i][k]+f[j][k-1])%1000007;
}
}
}
cout<<f[m][n]<<"\n";
return 0;
}
吼吼吼！
共 1 条回复
What's up.