HDU 5234 背包。
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
The garden is splited into n*m grids. In each grids, there is a cake. The weight of cake in the i-th row j-th column is ${w_{ij}}$ kilos, Gorwin starts from the top-left(1,1) grid of the garden and walk to the bottom-right(n,m) grid. In each step Gorwin can go to right or down, i.e when Gorwin stands in (i,j), then she can go to (i+1,j) or (i,j+1) (However, she can not go out of the garden).
When Gorwin reachs a grid, she can eat up the cake in that grid or just leave it alone. However she can’t eat part of the cake. But Gorwin’s belly is not very large, so she can eat at most K kilos cake. Now, Gorwin has stood in the top-left grid and look at the map of the garden, she want to find a route which can lead her to eat most cake. But the map is so complicated. So she wants you to help her.
Input
In the next n lines, the i-th line contains m integers ${w_{i1}},{w_{i{\rm{2}}}},{w_{i3}}, \cdots {w_{im}}$ which describes the weight of cakes in the i-th row
Please process to the end of file.
[Technical Specification]
All inputs are integers.
1<=n,m,K<=100
1<=${w_{ij}}$<=100
Output
Sample Input
1 1 2
3
2 3 100
1 2 3
4 5 6
Sample Output
0
16
Hint
In the first case, Gorwin can’t eat part of cake, so she can’t eat any cake. In the second case, Gorwin walks though below route (1,1)->(2,1)->(2,2)->(2,3). When she passes a grid, she eats up the cake in that grid. Thus the total amount cake she eats is 1+4+5+6=16.
#include<stdio.h>
#include<string.h>
#include<math.h>
#define max(a, b)(a > b ? a : b)
#define N 106
int dp[N][N][N];
int a[N][N];
int main()
{
int i, j, n, m, k, l, aa, b, c, d;
while(scanf("%d%d%d", &n, &m, &k) != EOF)
{
memset(dp, 0, sizeof(dp));
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
for(l = 0; l <= k; l++)
{
aa = b = c= d;
aa = dp[i][j-1][l];
b = dp[i-1][j][l];
if(l >= a[i][j])//如果物品的体积小于等于当前背包的体积,。
{
c = dp[i][j-1][l-a[i][j]]+a[i][j];//放入后上边物品的价值。
d = dp[i-1][j][l-a[i][j]]+a[i][j];//放入后左边物品的价值。
dp[i][j][l] = max(max(aa, b),max(c, d));
}
else//如果物品的体积大于当前背包的体积, 就不放, 判断左边的点和上边的点那个大。
dp[i][j][l] = max(aa, b);
}
printf("%d\n", dp[n][m][k]);
}
return 0;
}
最新文章
- 手动安装Oracle的Maven依赖
- Win10 UI动画
- 2013 duilib入门简明教程 -- 复杂控件介绍 (13)
- 我心中的核心组件(可插拔的AOP)~第四回 异常拦截器
- 字节流和字符流(BufferedReader类和BufferedWriter类)
- sql语句练习50题
- C#记录对象的变化
- 使用 IL 实现类型转换
- Redis 在windows环境下安装
- ASP.NET使用Jquery-Ajax向ashx传递参数中文出现乱码
- maven install 报错Could not calculate build plan: Plugin org.apache.maven.plugins:maven-resources-plugin
- js基础例子dom+原型+oop基础知识记录01
- hihoCoder 1388 Periodic Signal(FFT)
- UDP 通信
- VR的发展历程-VR全景智慧城市
- xml解析案例
- 腾讯云服务器php+mysq+nginx配置出现的问题及解决方法(亲测)
- APP性能测试(CPU)
- nodeJS基于smtp发邮件
- setInterval()使用时易疏忽的点