@[Alex_Wei](/user/123294) @[_bzy](/user/213388) @[Polaris_Australis_](/user/576737)
by Elairin176 @ 2024-08-04 16:00:44
@[Eirin_Yagokoro](/user/592238) 大佬又开始了
by I_never_left @ 2024-08-04 16:13:39
qpzc
by Alcl000000 @ 2024-08-04 16:54:51
哦对了，还要开大内存，开到 512MB.
by Elairin176 @ 2024-08-04 18:37:08
↑此题可以通过滚动数组的方式降低空间复杂度，故无需开 512MB。
但是这会大大提高题目难度，具体是否修改恳请管理斟酌。
by Elairin176 @ 2024-08-05 20:38:24
求助
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int const maxn=5e3+10,maxm=1e2+10,inf=2100000000;
int n,s,dp[maxn][maxn][2],lsum[maxn],rsum[maxn];
struct node{
int v,w;
}a[maxn];
main(){
cin>>n>>s;
for(int i=1;i<=n;i++) cin>>a[i].v>>a[i].w;
for(int i=1;i<=s;i++) lsum[i]=lsum[i-1]+a[i].w;
for(int i=n;i>=s;i--) rsum[i]=rsum[i+1]+a[i].w;
dp[s][s][0]=dp[s][s][1]=0;
for(int i=s;i>=1;i--) for(int j=s;j<=n;j++){
if(i==s&&j==s) continue;
dp[i][j][1]=dp[i][j][0]=inf;
if(i!=s) dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1].v-a[i].v)*(lsum[i]+rsum[j+1]),dp[i+1][j][1]+(a[j].v-a[i].v)*(lsum[i]+rsum[j+1]));
if(j!=s) dp[i][j][1]=min(dp[i][j-1][1]+(a[j].v-a[j-1].v)*(lsum[i-1]+rsum[j]),dp[i][j-1][0]+(a[j].v-a[i].v)*(lsum[i-1]+rsum[j]));
dp[i][j][1]=min(dp[i][j][1],dp[i][j][0]+(a[j].v-a[i].v)*(lsum[i-1]+rsum[j+1])),dp[i][j][0]=min(dp[i][j][0],dp[i][j][1]+(a[j].v-a[i].v)*(lsum[i-1]+rsum[j+1]));
}
cout<<min(dp[1][n][0],dp[1][n][1]);
return 0;
}
```
by hxuwna @ 2024-08-11 14:24:09
加强版的
by hxuwna @ 2024-08-11 14:24:44
@[hxuwna](/user/767125) inf 小了。
by Elairin176 @ 2024-08-11 16:44:16
@[Eirin_Yagokoro](/user/592238) 过了，大佬nb
by hxuwna @ 2024-08-12 08:59:26
zc，顺便一问这道题怎么滚动数组啊，太弱了想不到QAQ
by Delete_error @ 2024-08-18 17:07:00