區(qū)間DP

每次決策時計算當(dāng)前決策對未來的影響

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1000+5; const int inf=1e9; int sum,s[N],f[N][N][2],x[N],n,y[N],st; bool vis[N][N][2]; int w(int i,int j){return sum-(s[j]-s[i-1]); } int dp(int l,int r,int pos){if(vis[l][r][pos])return f[l][r][pos];vis[l][r][pos]=1;if(l==r){return f[l][r][pos]=l==st?y[l]:-inf;}if(!pos)f[l][r][pos]=max(dp(l+1,r,0)-(x[l+1]-x[l])*w(l+1,r),dp(l+1,r,1)-(x[r]-x[l])*w(l+1,r))+y[l];else f[l][r][pos]=max(dp(l,r-1,0)-(x[r]-x[l])*w(l,r-1),dp(l,r-1,1)-(x[r]-x[r-1])*w(l,r-1))+y[r];return f[l][r][pos]; } struct Node{int x,y,v,flag;bool operator < (const Node &rhs)const{return x<rhs.x;} }hash[N]; int main(){//freopen("a.in","r",stdin);int n,x0;scanf("%d%d",&n,&x0);for(int i=1;i<=n;i++)scanf("%d",&hash[i].x);for(int i=1;i<=n;i++)scanf("%d",&hash[i].y);for(int i=1;i<=n;i++)scanf("%d",&hash[i].v);hash[++n]=(Node){x0,0,0,1};sort(hash+1,hash+1+n);for(int i=1;i<=n;i++){x[i]=hash[i].x;y[i]=hash[i].y;if(hash[i].flag)st=i;s[i]=s[i-1]+hash[i].v;sum+=hash[i].v;}printf("%.3lf\n",max(dp(1,n,0),dp(1,n,1))/1000.0);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2037: [Sdoi2008]Sue的小球的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。