解题思路:看了一眼数据这么小想到可以利用DP解决 想出dp表达式idp[i][j][t][c];//坐标为 i j 最大价值为t 身上宝物为c时候的状态数量 分两种情况转移 1.没选当前格子的 2.能够选当前格子的
注意事项:记得开long long
参考代码:
#include<bits/stdc++.h>
#define int long long
#define MO 1000000007
using namespace std;
int dp[55][55][15][15];//坐标为 i j 最大价值为t 身上宝物为c时候的状态数量
int n,m,k,ma[55][55];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ma[i][j];
ma[i][j];
ma[i][j]++;
}
}
dp[1][1][ma[1][1]][1]=dp[1][1][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int t=0;t<=12;t++){
for(int c=0;c<=k;c++){
//先不选
dp[i][j][t][c]=(dp[i][j][t][c]+dp[i-1][j][t][c]+dp[i][j-1][t][c])%MO;
//如果能选
if((ma[i][j])==t&&c>0){
//记得包括多种情况
for(int temp=0;temp<t;temp++){
dp[i][j][t][c]=(dp[i][j][t][c]+dp[i-1][j][temp][c-1])%MO;
dp[i][j][t][c]=(dp[i][j][t][c]+dp[i][j-1][temp][c-1])%MO;
}
}
}
}
}
}
int ans=0;
for(int i=0;i<15;i++){ans+=dp[n][m][i][k];ans%=MO;}
cout<<ans<<endl;
}
0.0分
0 人评分
分糖果 (C++代码)浏览:865 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1084 |
C语言程序设计教程(第三版)课后习题5.7 (C++代码)浏览:849 |
C语言训练-计算1~N之间所有奇数之和 (C语言代码)浏览:651 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:960 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:840 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:1329 |
printf基础练习2 (C语言代码)浏览:746 |
回文数字 (C语言代码)浏览:2510 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1420 |