hdu 1224 Free DIY Tour(dp)

小灰灰 2024-02-17 19:15 18阅读 0赞

题意：求从城市1到城市n+1的最大兴趣值，不能从城市编号数字大的到数字小的。

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=100+10;
    int dp[maxn];
    int p[maxn];
    int path[maxn];
    int g[maxn][maxn];
    int n;
    
    void print(int t){
    	if(path[t])print(path[t]);
    	if(t!=n+1)printf("%d->",t);
    }
    int main(){
    	int T;
    	int count1=0;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d",&n);
    		for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    		int m;
    		scanf("%d",&m);
    		memset(dp,0,sizeof(dp));
    		memset(g,0,sizeof(g));
    		memset(path,0,sizeof(path));
    		for(int i=0;i<m;i++){
    			int a,b;
    			scanf("%d%d",&a,&b);
    			g[a][b]=1;
    		}
    		
    		p[n+1]=0;    //这里不要忘了 
    		for(int i=1;i<=n+1;i++){
    			for(int j=1;j<i;j++){
    				if(g[j][i] && p[i]+dp[j]>dp[i]){
    					dp[i]=p[i]+dp[j];
    					path[i]=j;
    				}
    			}
    		}
    		printf("CASE %d#\n",++count1);
    		printf("points : %d\ncircuit : ",dp[n+1]);
    		print(n+1); printf("1\n");
    		if(T)printf("\n");
    	} 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 1224 Free DIY Tour(dp)

题意：求从城市1到城市n+1的最大兴趣值，不能从城市编号数字大的到数字小的。 AC代码如下： include<cstdio> include<cstring

小灰灰/ 2024年02月17日 19:15/ 0 赞/ 19 阅读

相关精选汇总 | 硬件DIY

关注+星标公众号，不错过精彩内容 ![3fef35fb45116624d6df6d6980707a7e.gif][] 作者 | strongerHuang 微信公众号 |

深碍√TFBOYSˉ_/ 2022年10月23日 11:09/ 0 赞/ 159 阅读

相关 free命令

free命令可以显示Linux系统中空闲的、已用的物理内存及swap内存,及被内核使用的buffer。在Linux系统监控的工具中，free命令是最经常使用的命令之一。 1．

太过爱你忘了你带给我的痛/ 2022年09月17日 14:20/ 0 赞/ 174 阅读

相关 Eclipse DIY(转截)

Eclipse DIY 我用过的最好的IDE Eclipse是Java社区最出名的Open Source项目之一，自从下载使用之后便爱不释手。在此我就

红太狼/ 2022年08月25日 02:13/ 0 赞/ 106 阅读

相关 Free Loop

Free Loop （管不住的音符）　　I'm a little used to calling outside your name 　　如果不喊出你的名字，我在

分手后的思念是犯贱/ 2022年07月12日 13:39/ 0 赞/ 162 阅读

相关 HDU 1224(动态规划)

问题描述: Weiwei is a software engineer of ShiningSoft. He has just excellently fulfilled a

桃扇骨/ 2022年06月02日 11:39/ 0 赞/ 143 阅读

相关 hdu-1224-Free DIY Tour

Free DIY Tour Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (

小鱼儿/ 2022年05月20日 10:10/ 0 赞/ 127 阅读

相关 1224: 画表格

题目描述天外来客这学期正在学计算机图形学这门课程。通过这门课程的学习，天外来客已经掌握了如何用计算机来画线，圆，矩形等基本图形。最近，老师布置了一个画表格的作业。这个问

超、凢脫俗/ 2022年05月18日 07:37/ 0 赞/ 120 阅读

相关编译器DIY——词法分析

在上一篇文章中已经介绍了读文件的操作，那么这一篇文章中将会细致解释词法分析。在源文件里解析出的单词流必须识别为保留字，标识符，常量，操作符和界符五大类 1.显然我们须要列

素颜马尾好姑娘i/ 2022年03月27日 09:44/ 0 赞/ 208 阅读

相关 Free

Free无论是译作“自由”还是“免费”对于使用者来说似乎都有好处，但当自己处于开发者或开发厂商的角度，可能就是“双重标准”了，毕竟没有几个人能像Linus那样Just F...

小灰灰/ 2021年01月08日 14:04/ 0 赞/ 401 阅读