原来的原来这是个二维费用的DP、、、、、好吧 又一次显现了我的无知
题意很明显,必须买m张时间在L之内看完的电影票,使其价值最大。
好吧,就解释下二维DP的思想吧
所谓的二维费用,就是对于同个物品有两个不同的费用,需要进行约束,一种约束可以用一维数组来实现,显然,二维可以解决二维费用((*^__^*) 嘻嘻……好像是废话呢)。
知道这个 代码就很好写了
然而的然而 ,这里有个需要注意的,题目要求必须买m张电影票,也就是说,第一维数组必须是满的,即初始化的时候必须是负无穷大(若找最小值,则是正无穷大)。
唉,第一次这样初始化二维数组,有点木讷,这里特意标明下。
OK,附上代码:
//long long 最大表示10^19
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define Max 2147483648
struct info
{
int T;
int V;
}N[101];
int dp[105][1005];//记录i张票时间j可以买到的最大的价值
int main()
{
int t;
int i,j,k;
cin>>t;
while(t--)
{
int n,m,l;
cin>>n>>m>>l;//n场电影,必须买m场,最长花费l时间
for(i=0;i<n;i++)
{
cin>>N[i].T>>N[i].V;
}
// sort(N,N+n,cmp);
//初始化
memset(dp,0,sizeof(dp));
for(i=1;i<=m;i++)
for(j=0;j<=l;j++)
dp[i][j]=-Max;
for(i=0;i<n;i++)
{
for(j=m;j>0;j--)
{
for(k=l;k>=N[i].T;k--)
dp[j][k]=max(dp[j][k],dp[j-1][k-N[i].T]+N[i].V);
}
}
if(dp[m][l]<0) cout<<"0"<<endl;
else cout<<dp[m][l]<<endl;
}
return 0;
}
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
杭州电子科技大学online judge (hdu)第十一卷 2000 - 2099 题目集 doc 格式的,希望大家喜欢!
解题报告|ACM|程序设计参考程序以及题目的分析
ACM程序设计题目分析以及AC的源码
ACM题库,一些题目和答案,以及解题报告,传上来共享
最精准的答案(本人做对的题目拿上来给大家呈现)!不要忘记是C++编的
杭电OnlineJudge 200-2099的解题报告
HDU的一题........HDU DP动态规
我去年暑假花了5天,把杭电ACM网站上2000到2099这100道题全AC了,又花了10来天精心写解题报告。 里面包括题目、解题思路、编程技巧以及参考源码。所有代码都是使用C/C++写的。 最近整理资料时无意间发现,打包...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU 里面的2000~2099道题目的源码。谢谢支持
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
杭电ACM2000-2099题的解题报告