CF372C Watching Fireworks is Fun （单调队列优化dp）

Problem - 372C - Codeforces 

题目大意：

城镇中有n个位置，有 m个烟花要放。第i个烟花放出的时间记为 t，放出的位置记为a 。如果烟花放出的时候，你处在位置x，那么你将收获b-abs(a-x)点快乐值。

初始你可在任意位置，你每个单位时间可以移动不大于d 个单位距离。现在你需要最大化你能获得的快乐值。

(1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).

题解：

怎么dp呢......设一维时间，一维位置，差不多了。但是位置有点大，如果i为时间，j为位置，从k来，       空间300*150000开不出来。

怎么办呢.......好像可以滚动欸，那就是2*150000了，空间解决，那么两个位置150000*150000两个for循环肯定寄。怎么优化呢......

发现枚举i，j后，k好像可以一直维护在决策范围内，最优的话可以用单调队列维护，那么时间也解决了。

/*keep on going and never give up*/#includeusing namespace std;#define int long long#define ll long long#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read(){    int x=0,k=1; char c=getchar();    while(c'9'){if(c=='-')k=-1;c=getchar();}    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();    return x*k;}const double E = exp(1);const double PI = acos(-1.0);const int mod=1e9+7; const int maxn = 150000 + 10;const int maxm = 300 + 10;ll dp[2][maxn];ll a[maxm], b[maxm], t[maxm];int n, m, d;int que[maxn];int fl = 1;void init() {  memset(dp, 0x3f, sizeof(dp));  memset(que, 0, sizeof(que));  for(int i=1;i<=n;i++)dp[0][i]=0;  fl=1;}void solve() {  init();  for (int i=1;i<=m;i++) {    int l=1,r=0,k=1;    for (int j=1;j<=n;j++) { for (;k<=min(1ll*n,j+d*(t[i]-t[i-1]));k++) { while (l<=r&&dp[fl^1][que[r]]<=dp[fl^1][k]) r--; que[++r]=k;      }      while(l<=r&&que[l]>n>>m>>d;  for (int i=1;i>a[i]>>b[i]>>t[i];  solve();  ll ans=-1e18;  for(int i=1;i<=n;i++) ans=max(ans,dp[fl^1][i]);  cout<<ans<<endl;  return 0;  }

ps：没想到单调队列还不会，只会单调栈，这里还是用数组模拟的，用duque也可以，学一手也好。