【BZOJ2037】Sue的小球（動態規劃）

題面

BZOJ

題解

莫名想到這道題目
很明顯是一樣的
設\(f[i][j][0/1]\)表示已經接到了\(i～j\)這一段的小球
當前在\(i\)或者在\(j\)的最小費用
這個費用是隨著時間增長，沒有被接到的小球產生的

這樣就可以避免存下時間
提前就把費用減去

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; inline int read() {int x=0,t=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t; } double f[1010][1010][2]; struct Ege{double x,y,v;}a[1010]; int n; double S[1010]; double tot; bool operator<(Ege a,Ege b){return a.x<b.x;} int main() {n=read();double X=read();for(int i=1;i<=n;++i)a[i].x=read();for(int i=1;i<=n;++i)a[i].y=read();for(int i=1;i<=n;++i)a[i].v=read();sort(&a[1],&a[n+1]);for(int i=1;i<=n;++i)S[i]=S[i-1]+a[i].v;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)f[i][j][0]=f[i][j][1]=1e18;int l1=lower_bound(&a[1],&a[n+1],(Ege){X,0,0})-a;f[l1][l1][0]=f[l1][l1][1]=1.0*abs(X-a[l1].x)*S[n];l1--;f[l1][l1][0]=f[l1][l1][1]=1.0*abs(X-a[l1].x)*S[n];for(int len=2;len<=n;++len)for(int i=1;i<=n-len+1;i++){int j=i+len-1;f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+1.0*(a[i+1].x-a[i].x)*(S[i]+S[n]-S[j]));f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+1.0*(a[j].x-a[i].x)*(S[i]+S[n]-S[j]));f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+1.0*(a[j].x-a[i].x)*(S[i-1]+S[n]-S[j-1]));f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+1.0*(a[j].x-a[j-1].x)*(S[i-1]+S[n]-S[j-1]));}for(int i=1;i<=n;++i)tot+=a[i].y;printf("%.3lf\n",(tot-min(f[1][n][0],f[1][n][1]))/1000.00);return 0; }

轉載于:https://www.cnblogs.com/cjyyb/p/8312694.html

總結

以上是生活随笔為你收集整理的【BZOJ2037】Sue的小球（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。