[DP/單調隊列]BZOJ 2059 [Usaco2010 Nov]Buying Feed 購買飼料

首先我想吐槽的是題目并沒有表明數據范圍。。。

?

這個題目 DP方程并不難表示。

dp[i][j]表示前i個地點攜帶了j個貨物的最小花費

dp[i][j] = dp[i-1][k] + (j-k) * cost + j*j*(leng[i]-leng[i-1])

如果你這樣直接提交上去，恭喜你超時！！！ 因為這個時間復雜度是 O(n*k^2)

所以我們需要優化一下，可以發現式子可以化簡為：

dp[i][j] = dp[i-1][k] - k * cost? + j*j*(leng[i]-leng[i-1]) +??j*cost?

dp[i][j] = dp[i-1][k] - k * cost 這一部分可以只是與k有關，這里我們可以用單調隊列進行優化，使其保持 最小值。

?

坑點1：注意數據范圍

坑點2：注意初始化

?

/**************************************************************Problem: 2059User: LYFerLanguage: C++Result: AcceptedTime:480 msMemory:61600 kb
****************************************************************/#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>#define mp(a,b) make_pair(a,b)
#define fr(a,b,c) for(int c=a;c<=b;++c)using namespace std;
typedef long long ll;const ll INF = 1e16;
ll dp[777][10005];
int n,e,k;inline int Read(){int ans = 0, flag = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch=='-') flag=-1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans = ans * 10 + ch - '0';ch = getchar();}return ans * flag;
}struct task{ll now,num,cost;bool operator <(const task &x) const{return now < x.now;}
}feed[505];struct DanDiao{deque< pair<ll,int> >Q;void insert(ll x,int y){while( !Q.empty() && Q.back().first >= x) Q.pop_back();Q.push_back( mp(x,y) );}void erase(int y){while( !Q.empty() && Q.front().second <= y) Q.pop_front();}
}DD;int main(){k = Read();e = Read();n = Read();fr(1,n,i){feed[i].now = Read();feed[i].num = Read();feed[i].cost = Read();}sort(feed+1,feed+1+n);feed[++n] = (task){e,0,0};for(int i=0;i<=n;i++){for(int j=0;j<=k;j++){dp[i][j] = INF;}}dp[1][0] = 0;fr(2,n,i){DD.Q.clear();int r = 0;fr(0,k,j){while(r <= j) DD.insert(dp[i-1][r] - r*feed[i-1].cost , r) , r++;DD.erase(j - feed[i-1].num - 1);if( DD.Q.empty()) dp[i][j] = INF;else dp[i][j] = DD.Q.front().first+j*feed[i-1].cost+j*j*(feed[i].now-feed[i-1].now);}}/*for(int i=1;i<=n;i++){for(int j=0;j<=k;j++){printf("dp[%d][%d]:%d\n",i,j,dp[i][j]);}}*/printf("%lld\n",dp[n][k]);return 0;
}

?