part 1 暴力
不难发现有一个 \(\mathcal O(K^2n)\) 的基础 dp：
\[f_{i,j+l}=\min(f_{i,j+l},f_{i-1,j}+(x_i-x_{i-1})\times j\times j+c_i\times l);
\]
这其中 \(f\) 代表在第 \(i\) 个点已经买了 \(j+l\) 个，其中当前第 \(i\) 个点买了 \(l\) 个，前 \(i-1\) 个点买了 \(j\) 个的最小价值。
这样的话可以水到 90pts，但是如果是联赛的话应该没有这么高的暴力分。
code
#include<bits/stdc++.h>
#define int short
#define N 105
using namespace std;
int E,K,f[N],n,c[N],x[N],dp[502][N],sum[N];
struct mm
{int c,x,f;}p[N];
namespace AYX
{ inline bool cmp(mm i,mm j){return i.x>j.x;}
inline short main()
{ //freopen("c.in","r",stdin);
//freopen("2.out","w",stdout);
scanf("%lld%lld%lld",&K,&E,&n);
for(int i=1;i<=n;++i)scanf("%lld%lld%lld",&p[i].x,&p[i].f,&p[i].c);
memset(dp,0x3f3f3f3f,sizeof(f));
dp[1][0]=0;
sort(p+1,p+1+n);
p[n+1].x=E;p[n+1].f=K;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+p[i].f;
for(int i=2;i<=n;++i)
for(int j=0;j<=min(K,sum[i]);++j)
for(int l=0;l<=p[i-1].f;++l)
{ if(l+j>K) braek;
dp[i][j+l]=min(dp[i][j+l],dp[i-1][j]+p[i-1].c*l+(j+l)*(j+l)*(p[i].x-p[i-1].x));
}
printf("%ldl\n",dp[n+1][K]);
return 0;
}
}
signed main()
{return AYX::main();
}
part 2 单调队列优化 dp
对式子进行转换，我们能够得到：
\[f_{i,k}=\min(f_{i,j},f_{i-1,j}+(x_i-x_{i-1})\times j\times j-c_i\times j)+c_i
\times k;\]
这样 \(c_i\times j\) 会变成一个常数，式子只和 \(i\) 和 \(j\) 有关。
采用单调队列使复杂度降到 \(\mathcal O(Kn)\) 稳稳通过。
当然还可以用二进制优化背包来降复杂度，只不过不如单调队列快。
code
#include<bits/stdc++.h>
#define int short
#define N 105
using namespace std;
int E,K,f[N],n,c[N],x[N],dp[502][N],sum[N],dui[N],head,tail;
struct mm
{int c,x,f;}p[N];
namespace AYX
{ inline bool cmp(mm i,mm j){return i.x<j.x;}
inline int calc(int i,int j)
{return dp[i-1][j]+(p[i].x-p[i-1].x)-p[i].c;}
inline short main()
{
scanf("%ldl%ldl%ldl",&K,&E,&n);
for(int i=1;i<=n;++i)scanf("%ldl%ldl%ldl",&p[i].x,&p[i].f,&p[i].c);
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0][0]=0;
sort(p+1,p+1+n);
for(int i=1;i<=n;++i)
{ head=0;tail=1;
for(int j=0;j<=K;++j)
{ int val=calc(i,j);
while(head<=tail and calc(i,dui[tail])>val)tail--;
while(head<=tail and j-p[i].f<dui[head])++head;
dui[+tail+]=j;
dp[i][j]=calc(i,dui[tali])+p[i].c*j;
}
}
printf("%ldl\n",dp[n][K]+(E-p[n].x)*K*K);
return 1;
}
}
signed main()
{return AYX::main();
}