POJ 3257 DP
2024-09-02 00:19:33
题意:
思路:
用vector存上本出发点能到的地方&成本&有趣指数(用结构体保存)
然后DP就好了
f[i][j]表示到了i 成本为j的有趣指数最大是多少
f[vec[i][k].end][j+vec[i][k].c]=max(f[vec[i][k].end][j+vec[i][k].c],f[i][j]+vec[i][k].f);
//By SiriusRen
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int l,n,b,f[1005][1005],ans;
struct Node{int f,c,start,end;}node[10005];
vector<Node>vec[1005];
int main(){
scanf("%d%d%d",&l,&n,&b);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&node[i].start,&node[i].end,&node[i].f,&node[i].c);
node[i].end+=node[i].start;
vec[node[i].start].push_back(node[i]);
}
f[0][0]=1;
for(int i=0;i<=l;i++){
for(int j=b;j>=0;j--){
if(!f[i][j])continue;
for(int k=0;k<vec[i].size();k++){
if(j+vec[i][k].c>b||!f[i][j])continue;
f[vec[i][k].end][j+vec[i][k].c]=max(f[vec[i][k].end][j+vec[i][k].c],f[i][j]+vec[i][k].f);
}
}
}
for(int i=0;i<=b;i++)ans=max(ans,f[l][i]);
if(!ans)puts("-1");
else printf("%d\n",ans-1);
}
最新文章
- Xamarin Android 应用程序内图标上数字提示
- plist
- DataItem,gridview,repeater数据控件数据绑定
- 快速与MySQL交互,使用XMAPP打开MySQL数据库,并用shell进行与MySQL交互<;Window 10>;
- 软件工程(QLGY2015)第一次作业小结(含成绩)
- 部署在IIS上的网站如何调试
- 如何在WPF应用程序中使用视频处理控件TVideoGrabber
- zabbix安装,关闭SELinux
- linux常见驱动修改
- [转] Web前端优化之 Javascript篇
- Flex友好提示、警告
- ORA-00911: invalid character
- perl 登录某网站
- 扣出的图片无法调整大小 photoshop mac版本
- Android Testing Point
- 使用.Net+非关系型数据库MongoDB 实现LBS商家按距离排序_按离我最近排序
- Elasticsearch笔记六之中文分词器及自定义分词器
- python --- 快速排序算法
- 讨论下python中全局变量的使用
- 好用的 FTP 软件之 FileZilla 技巧教程