本文共 1639 字，大约阅读时间需要 5 分钟。
$dp$，斜率优化。
和基本上是一样的。这题还比那题简单，得到斜率的式子很方便。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-10;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}int T,n,m;long long dp[10010][5010];long long x[10010];int q[10010],f1,f2;bool delete1(int t,int a,int b,int c){ if(dp[b][t]+x[b+1]*x[b+1]-dp[a][t]-x[a+1]*x[a+1]<2*x[c]*(x[b+1]-x[a+1])) return 1; return 0;}bool delete2(int t,int a,int b,int c){ if((dp[c][t]+x[c+1]*x[c+1]-dp[b][t]-x[b+1]*x[b+1])*(x[b+1]-x[a+1])<= (dp[b][t]+x[b+1]*x[b+1]-dp[a][t]-x[a+1]*x[a+1])*(x[c+1]-x[b+1]) ) return 1; return 0;}int main(){ scanf("%d",&T); int cas=1; while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&x[i]); sort(x+1,x+1+n); for(int i=1;i<=n;i++) dp[i][1]=(x[i]-x[1])*(x[i]-x[1]); for(int j=2;j<=m;j++) { f1=f2=0; q[f2]=j-1; for(int i=j;i<=n;i++) { while(1) { if(f2-f1+1<2) break; if(delete1(j-1,q[f1],q[f1+1],i)) f1++; else break; } dp[i][j]=dp[q[f1]][j-1]+(x[i]-x[q[f1]+1])*(x[i]-x[q[f1]+1]); while(1) { if(f2-f1+1<2) break; if(delete2(j-1,q[f2-1],q[f2],i)) f2--; else break; } f2++; q[f2]=i; } } printf("Case %d: %lld\n",cas++,dp[n][m]); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/6351508.html