免费发外链的网站,网站建设费用有哪些方面,网站 特效都是用什么软件做的,企业文化培训心得体会甲虫
luogu 4870
题目大意#xff1a;
在一个坐标轴上有n个露珠#xff0c;每个露珠有m个水分#xff0c;露珠会每隔一个时间单位就消失一点水分#xff0c;现在有一只甲虫从原点出发#xff0c;甲虫的移动速度是一个单位时间移动一个单位的距离#xff0c;甲虫没碰到…甲虫
luogu 4870
题目大意
在一个坐标轴上有n个露珠每个露珠有m个水分露珠会每隔一个时间单位就消失一点水分现在有一只甲虫从原点出发甲虫的移动速度是一个单位时间移动一个单位的距离甲虫没碰到一个露珠就可以“秒杀”它问甲虫最多可以迟到多少水分
前言
本题是本蒟蒻AC的第一道紫题(▽)
输入样例
3 15
6
-3
1输出样例
25数据范围
0≤n≤300,1≤m≤1,000,000,−10,000≤x1,x2,…,xn≤10,0000 \le n \le 300,1 \le m \le 1,000,000,-10,000 \le x_1,x_2,\dots,x_n \le 10,0000≤n≤300,1≤m≤1,000,000,−10,000≤x1,x2,…,xn≤10,000 对于所有 i≠j,xi≠xj。i \ne j,x_i \ne x_j。ij,xixj。
解题思路
我们可以求最小散失水分以此来算出最大水分 首先设f[i][j][0/1]f[i][j][0/1]f[i][j][0/1]为吃掉第iii到第jjj个水分的最小散失然后我们可以得出一下状态转移方程 {f[i][j][0]min(f[i1][j][0](k−len1)∗(a[i1]−a[i]),f[i1][j][1](k−len1)∗(a[j]−a[i]))f[i][j][1]min(f[i][j−1][1](k−len1)∗(a[j]−a[j−1]),f[i][j−1][0](k−len1)∗(a[j]−a[i]))\left\{\begin{matrix}f[i][j][0]min(f[i1][j][0](k-len1)*(a[i1]-a[i]),f[i1][j][1](k-len1)*(a[j]-a[i]))\\ f[i][j][1]min(f[i][j-1][1](k-len1)*(a[j]-a[j-1]),f[i][j-1][0](k-len1)*(a[j]-a[i]))\end{matrix}\right.{f[i][j][0]min(f[i1][j][0](k−len1)∗(a[i1]−a[i]),f[i1][j][1](k−len1)∗(a[j]−a[i]))f[i][j][1]min(f[i][j−1][1](k−len1)∗(a[j]−a[j−1]),f[i][j−1][0](k−len1)∗(a[j]−a[i])) 其中k代表要吃多少个水滴len表示已经吃了多少个水滴然后它表示的就是从左边和右边分别往两个方向走
代码 #includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n,o,m,ans,a[350],f[350][350][2];
int main()
{scanf(%d %d,n,m);for (int i1;in;i)scanf(%d,a[i]);a[n]0;//从0出发sort(a1,a1n);for (int i1;in;i)if (a[i]0) //找到0的位置{oi;break;}for (int k1;kn;k){memset(f,127/3,sizeof(f));f[o][o][0]0;//初值f[o][o][1]0;for (int len2;lenk;len)for (int i1;in-len1;i){int jilen-1;f[i][j][0]min(f[i1][j][0](k-len1)*(a[i1]-a[i]),f[i1][j][1](k-len1)*(a[j]-a[i]));//状态转移k-len1f[i][j][1]min(f[i][j-1][1](k-len1)*(a[j]-a[j-1]),f[i][j-1][0](k-len1)*(a[j]-a[i]));ansmax(ans,(len-1)*m-min(f[i][j][1],f[i][j][0]));//取最优答案}}printf(%d,ans);
}
