二次联通门 : cogs 999. [東方S2]雾雨魔理沙

摸你傻赛高!!

/*
cogs 999. [東方S2]雾雨魔理沙 原来以为是一道计算几何的题 可是细细一想发现。。
这就是一道dp 由于给定了斜率
每个点的b值也可以确定了(y = kx + b) 按照b值排序
后区间dp搞搞就好了 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath> #define PI 3.1415926 void read (int &now)
{
register char word = getchar ();
int temp = ;
for (now = ; !isdigit (word); word = getchar ())
if (word == '-')
temp = ;
for (; isdigit (word); now = now * + word - '', word = getchar ());
if (temp)
now = -now;
} double k; struct Point
{
int x, y; int value, mul; Point (int __x, int __y, int __v, int __m) : x (__x), y (__y), value (__v), mul (__m){}
Point () {} bool operator < (const Point &now) const
{
return (this->y - (this->x * k)) < (now.y - (now.x * k));
}
}; #define Max 2008
Point point[Max]; int _sum[Max], _mul[Max];
double dp[Max]; inline double max (double a, double b)
{
return a > b ? a : b;
} #define Cogs int main (int argc, char *argv[])
{
#ifdef Cogs freopen ("marisa.in", "r", stdin);
freopen ("marisa.out", "w", stdout); #endif int N;
read (N);
register int i, j; for (i = ; i <= N; ++ i)
read (point[i].x), read (point[i].y), read (point[i].value), read (point[i].mul); scanf ("%lf", &k);
k = tan (k / * * PI); std :: sort (point + , point + + N); for (i = ; i <= N; ++ i)
{
_sum[i] = _sum[i - ] + point[i].value;
_mul[i] = _mul[i - ] + point[i].mul; dp[i] = ; for (j = ; j <= i; ++ j)
dp[i] = max (dp[i], dp[j - ] + double(_sum[i] - _sum[j - ]) * (_mul[i] - _mul[j - ]) / (i - j + ));
} printf ("%.3lf", dp[N]); return ;
}

最新文章

  1. 冒烟测试 smoking test
  2. javascript高级编程3第三章:基本概念 本章内容 语法 数据类型 流控制语句 函数
  3. 学习ASP.NET MVC(四)——我的第一个ASP.NET MVC 实体对象
  4. LYDSY模拟赛day3 涂色游戏
  5. 快速认识ELK中的L - Logstash
  6. DiskFileItemFactory类---分析及运用
  7. 540A: Combination Lock
  8. oracle 的 regexp_substr()的用法
  9. CN_Week1_Receptive_Field
  10. 使用Ant打包Web前台程序
  11. SpringBoot的HelloWorld 应用及解释
  12. CSScript 使用纪要
  13. POJ2386----Lake Counting
  14. jquery.ajax与axios及定义拦截器
  15. 第一周java测验感想
  16. Dubbo源码学习--优雅停机原理及在SpringBoot中遇到的问题
  17. process information unavailable 的解决办法
  18. TCP握手和传输的一次观察
  19. Xilinx FPGA 的PCIE 设计
  20. SIM900A模块HTTP相关调试笔记

热门文章

  1. kubernetes(k8s)集群安装calico
  2. AppTheme属性设置集合
  3. pytest之mark功能
  4. java 枚举示例
  5. Django---Django的ORM的一对多操作(外键操作),ORM的多对多操作(关系管理对象),ORM的分组聚合,ORM的F字段查询和Q字段条件查询,Django的事务操作,额外(Django的终端打印SQL语句,脚本调试)
  6. 走一次HashMap的存取
  7. React Children 使用
  8. Beego 学习笔记13:Api编写
  9. Beego 学习笔记9:Boostrap使用介绍
  10. psexec与wmi在内网渗透的使用