我试了一下，把您的long double改成double 交换dp和solve数组的维数(dp[N][205] to dp[205][N])就不会超时了 但是wa了一个点
by Killer_joke @ 2022-12-30 12:29:04
给您调过了 把数组维数交换了一下 然后用define代替了函数
```cpp
#include<bits/stdc++.h>
#define ld double
#define ll long long
using namespace std;
const int N=1e5+5;
int n,k,a[N];
int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
void print(ll x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
ll sum[N],dp[205][N],q[N],head,tail,solve[205][N];
#define X(x) sum[x]
#define Y(x,d) dp[d][x]
#define slope(x,y,d) ((Y(x,d)-Y(y,d))/(X(x)-X(y)+(X(x)==X(y)?1e-9:0)))
#define calc(x,y,d) (dp[d][x]+(sum[y]-sum[x])*(sum[n]-sum[y]))
int main(){
//freopen("P3648_10.in","r",stdin);
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
for(int i=1;i<n;i++) dp[1][i]=sum[i]*(sum[n]-sum[i]);
for(int j=2;j<=k;j++){
head=1,tail=1;
q[1]=j-1;
for(int i=j;i<n;i++){
while(head<tail&&slope(q[head+1],q[head],j-1)>=sum[n]-sum[i]) head++;
dp[j][i]=calc(q[head],i,j-1);
solve[j][i]=q[head];
while(head<tail&&slope(q[tail],q[tail-1],j-1)<=slope(i,q[tail],j-1)) tail--;
q[++tail]=i;
}
}
int p=k;
for(int i=k;i<n;i++) if(dp[k][i]>dp[k][p]) p=i;
print(dp[k][p]);putchar('\n');
for(int i=k;i>=1;i--){
print(p);putchar(' ');
p=solve[i][p];
}
return 0;
}
```
by Killer_joke @ 2022-12-30 12:35:49
@[Killer_joke](/user/915814) 谢谢dalao
by Joestar @ 2022-12-30 13:22:55
@[Killer_joke](/user/915814) 为什么维数调换能降复杂度
by Bluebird_ @ 2023-03-11 20:21:26
@[Bluebird_](/user/213535) 访问连续的原因。
by Killer_joke @ 2023-03-11 21:20:12