解题思路:
设d[i][j][k][c]为走到(i,j)的时候，手上共K个物品，最大价值小于c
则d[i][j][k][c]转移方程是：
当前拿这个物品: s1= d[i-1][j][k-1][ w[i][j] ](从上边继承)+d[i][j-1][k-1][ w[i][j] ](从左边继承)
当前可以拿这个物品的条件是(c>a[i][j]&&k>0);
当前不拿物品 : s2= d[i-1][j][k][c](从上边继承)+d[i][j-1][k][c](从左边继承)
综合 d[i][j][k][c]= (s1+s2)%mod;
最大时间复杂度O(T)=O(i*j*k*c)=O(50*50*13*13)=O(422500)
本题AC时间:6ms;
注意事项:
初始化(i==0||j==0)的时候d[i][j][k][c]=0;
临界条件(i==1&&j==1)当k!=0或者 k==1且c>a[i][j]的时候设置为1，其他时候0；
答案是d[n][m][k][12];
参考代码:
#include <iostream>
#define _for(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long LL;
LL d[51][51][13][13],mod=1000000007;
int a[55][55];
int main() {
int n,m,K;
cin>>n>>m>>K;
_for(i,0,n)_for(j,0,m)cin>>a[i+1][j+1];
_for(i,1,n+1)_for(j,1,m+1)_for(k,0,K+1)_for(c,0,13){
LL na=0,buna=0;
if(i==1&&j==1){
if(!k||(k==1&&c>a[i][j]))d[i][j][k][c]=1;
continue;
}
if(k&&c>a[i][j])na=d[i-1][j][k-1][a[i][j]]+d[i][j-1][k-1][a[i][j]];
buna=d[i-1][j][k][c]+d[i][j-1][k][c];
d[i][j][k][c]=na+buna;
d[i][j][k][c]%=mod;
}
cout<<d[n][m][K][12]<<endl;
}0.0分
30 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复