解题思路:
注意事项:
为什么是四维?
因为里面有坐标i,j从两个方向来,还有k件物品需要维护,另外还有最后一件物品的价值c需要维护,因为需要c来比较,是否取不取,这样就可以表示出,这个问题了。
参考代码:
#include <stdio.h>
int dp[51][51][15][15];//dp[i][j][k][v]表示走到坐标为[i,j],取了k个数,最后一个物品的价值是v的方案数
int c[51][51]; //输入得n*m矩阵
int main()
{
int i,j,u,l;
int n,m,k;
scanf("%d%d%d",&n,&m,&k); //输入
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&c[i][j]);
}
}
dp[1][1][0][-1]=1; //不取左上角 边界赋值 避免无法取到价值为0的物品 将最后一个参数置为-1
dp[1][1][1][c[1][1]]=1;//取左上角
for(i=1;i<=n;i++) //遍历矩阵
{
for(j=1;j<=m;j++)
{
if(i==1&&j==1)
{
continue;
}
for(u=0;u<=k;u++) //枚举所有方案数 选了u个物品
{
for(l=-1;l<=12;l++) //枚举最后一个物品的价值(最大价值)
{
//不取(i,j)位置上的物品
int *num=&dp[i][j][u][l];
(*num)=((*num)+dp[i-1][j][u][l])%1000000007; //从上方下来
(*num)=((*num)+dp[i][j-1][u][l])%1000000007; //从左边过来
//取(i,j)位置上的物品
if(u>0&&c[i][j]==l) //枚举取当前[i,j]位置上的物品 当前物品的价值必须等于l
{
for(int w=-1;w<l;w++) //枚举上一个方案中小于最后一个物品价值的所有可能
{
(*num)=((*num)+dp[i-1][j][u-1][w])%1000000007;
(*num)=((*num)+dp[i][j-1][u-1][w])%1000000007;
}
}
}
}
}
}
int num=0;
for(i=-1;i<=12;i++)
{
num=(num+dp[n][m][k][i])%1000000007;
}
printf("%d",num);
return 0;
}
0.0分
1 人评分
C语言训练-8除不尽的数 (C++代码)浏览:652 |
Lucky Word (C++代码)浏览:928 |
点我有惊喜!你懂得!浏览:1324 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:967 |
sizeof的大作用 (C语言代码)浏览:1447 |
字符串输入输出函数 (C语言代码)浏览:2479 |
复数求和 (C语言代码)浏览:915 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:558 |
C语言训练-排序问题<1> (C语言代码)浏览:355 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:650 |