cogs 999. [東方S2]雾雨魔理沙
2024-09-03 09:31:53
二次联通门 : 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 ;
}
最新文章
- 冒烟测试 smoking test
- javascript高级编程3第三章:基本概念 本章内容 语法 数据类型 流控制语句 函数
- 学习ASP.NET MVC(四)——我的第一个ASP.NET MVC 实体对象
- LYDSY模拟赛day3 涂色游戏
- 快速认识ELK中的L - Logstash
- DiskFileItemFactory类---分析及运用
- 540A: Combination Lock
- oracle 的 regexp_substr()的用法
- CN_Week1_Receptive_Field
- 使用Ant打包Web前台程序
- SpringBoot的HelloWorld 应用及解释
- CSScript 使用纪要
- POJ2386----Lake Counting
- jquery.ajax与axios及定义拦截器
- 第一周java测验感想
- Dubbo源码学习--优雅停机原理及在SpringBoot中遇到的问题
- process information unavailable 的解决办法
- TCP握手和传输的一次观察
- Xilinx FPGA 的PCIE 设计
- SIM900A模块HTTP相关调试笔记
热门文章
- kubernetes(k8s)集群安装calico
- AppTheme属性设置集合
- pytest之mark功能
- java 枚举示例
- Django---Django的ORM的一对多操作(外键操作),ORM的多对多操作(关系管理对象),ORM的分组聚合,ORM的F字段查询和Q字段条件查询,Django的事务操作,额外(Django的终端打印SQL语句,脚本调试)
- 走一次HashMap的存取
- React Children 使用
- Beego 学习笔记13:Api编写
- Beego 学习笔记9:Boostrap使用介绍
- psexec与wmi在内网渗透的使用