做网站的项目开发计划书,html网站作业,wordpress数据库替换命令,网站建设和托管【题目描述】 CodeForces - 372CWatching Fireworks is Fun 题目的大概意思就是在一个编号为1…n的街道上现在按照时间顺序放烟花#xff0c;每个烟花获得的幸福感为b−abs(a−x)b-abs(a-x)b−abs(a−x)#xff0c;x为观看烟花的位置#xff0c;为了提升我们的幸福感#x…【题目描述】 CodeForces - 372CWatching Fireworks is Fun 题目的大概意思就是在一个编号为1…n的街道上现在按照时间顺序放烟花每个烟花获得的幸福感为b−abs(a−x)b-abs(a-x)b−abs(a−x)x为观看烟花的位置为了提升我们的幸福感我们可能会移动每个时间单位可以移动d长度现在问我们如果可以从任何一个地点开始观看烟花那么最后幸福感最大是多少 【题目分析】 连我这样不太会DP的人都能看出来这是一个DP按照放烟花的顺序dp[i][j]max(dp[i−1][k])b−abs(a[i]−x)dp[i][j]max ( dp[i-1][k] )b-abs(a[i]-x)dp[i][j]max(dp[i−1][k])b−abs(a[i]−x)其中k为所有可以到达j位置的点即i−t∗dlt;klt;it∗di-t*dlt;klt;it*di−t∗dkit∗dt是距离上次放烟花的时间差 可是这样做的话就需要对每一个烟花都遍历一个很大的区间应该会超时所以我们需要进行优化。 我们对于每个烟花我们都 用一个队列从前往后计算每个位置队列中保存的是能到达当前位置的所有区域中幸福感最大的按照从前往后的顺序如果后面某个位置的幸福感比前面的大就会将前面的弹出再将后面的放进去因为对于再往后的位置来讲后面这个幸福感更大的位置更有用前面的能到的后面的一定能到后面能到的前面的不一定能到而且前面的值还没有后面的大所以就不用考虑他了这也算是一种贪心吧 可能这样说有点绕可以先看代码注意理解双重循环的部分再回来看就应该很好理解了。 为了优化空间我们用一个二维的数组滚动的保存数据s0保存的是还没有放这个烟花的幸福感s1保存的是放了烟花后的幸福感对于下一个烟花将s0和s1调换就可以了最后s0保存的就是最后的结果查找最大值就可以了。 【AC代码】
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int MAXN150005;
ll dp[2][MAXN];
ll a,b,t,n,m,d,s0,s1,tt1,step;int main()
{scanf(%lld%lld%lld,n,m,d);s00; s11;while(m--){dequeint q;scanf(%lld%lld%lld,a,b,t);step(t-tt)*d; ttt;for(int i1,j1;in;i){for(;jistepjn;j){while(!q.empty() dp[s0][q.back()]dp[s0][j]) q.pop_back(); //后面的值还比前面的大前面的就没用了q.push_back(j); //不管有没有前面的弹出后面的暂时都是有用的除非更后面的将他挤出去}while(!q.empty() q.front()i-step) q.pop_front(); //如果队列刚开始的地方已经不能到达位置i就弹出。虽然可能他的幸福感很高但是对后面的值已经没有影响了。dp[s1][i]dp[s0][q.front()]b-abs(a-i);}swap(s0,s1);}ll ansdp[s0][1];for(int i2;in;i){if(dp[s0][i]ans) ansdp[s0][i];}printf(%lld,ans);return 0;
}【参考博客】 https://www.cnblogs.com/yehs/p/11331813.html
