这份代码可以AC通过,但是若将2处以下两行代码剪贴到1处,则无法通过,答案总是小一点,为什么???
40-42行的功能是将当前枚举到的k值加入单调队列中,若我在其执行之前转移,理论上我只要考虑的用当前的dp[i-1][k]来转移的情况就可以啊
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10010,inf=0x3f3f3f3f3f3f3f3f;
struct node{
int x,f,c;
node(){x=f=c=0;}
}a[505];
int K,E,n,dp[505][N],q[N],L,R;
bool cmp(node x,node y){return x.x<y.x;}
int dis(int x,int y){return abs(a[x].x-a[y].x);}
signed main()
{
ios::sync_with_stdio(0);
cin>>K>>E>>n;
for(int i=1;i<=n;++i)
cin>>a[i].x>>a[i].f>>a[i].c;
sort(a+1,a+1+n,cmp);
++n;
a[n].x=E;
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=n;++i)
{
R=0;L=1;
q[++R]=0;
dp[i][0]=0;
for(int k=1;k<=K;++k)
{
while(R-L+1>a[i-1].f)
++L;
/*1
int I=q[L];
dp[i][k]=min(dp[i-1][k]+k*k*dis(i-1,i),dp[i-1][I]+k*k*dis(i-1,i)+a[i-1].c*(k-I));
*/
while(R>=L&&dp[i-1][k]+(K-k+1)*a[i-1].c<=dp[i-1][q[R]]+a[i-1].c*(K-q[R]+1))
--R;
q[++R]=k;
// 2
int I=q[L];
dp[i][k]=min(dp[i-1][k]+k*k*dis(i-1,i),dp[i-1][I]+k*k*dis(i-1,i)+a[i-1].c*(k-I));
}
}
cout<<dp[n][K]<<"\n";
return 0;
}
/*
1 5 3
3 1 2
4 1 1000
1 1 1
*/