蒟蒻在基础DP上遇到困难
  • 板块灌水区
  • 楼主phil071128
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/8/18 14:15
  • 上次更新2023/11/6 20:02:35
查看原帖
蒟蒻在基础DP上遇到困难
306734
phil071128楼主2020/8/18 14:15
【题目描述】
平面上有n个敌方阵地,我们要派出轰炸机进行轰炸,由于基金短缺我们的轰炸机不能转弯?,只能在一条直线上进行轰炸,这里起点和终点是可以任意的。
这里只要敌方阵地在轰炸机的直线上就可以被炸毁,我们这里轰炸机只能飞一次,求最多能炸毁多少敌方阵地。
【输入格式】
输入文件C.in。
第一行一个整数n。
接下来n行每行两个整数表示阵地的坐标。
【输出格式】
输出文件C.out
一行一个整数表示最多能炸毁多少敌方阵地。
【样例输入1】
5
1 1
2 2
3 3
9 10
10 11
【样例输出1】
3

【数据范围】
对于 30% 数据 n<=10
对于 80% 数据 n<=500
对于 100% 数据  n<=1200,坐标在int范围内,可能为负。

推导了,遇到了困难

/*f[0][0]=s[0][0] 
	  f[1][0]=s[1][0]+f[0][0]
	  f[0][1]=s[0][1]+f[0][0]
	  f[1][1]=s[0][1]+max(f[0][0],max(f[0][1],f[1][0]).......)
	  
	*/
2020/8/18 14:15
加载中...