解題思路：動態規劃

遍歷點i，如果從前一個點i-1走到這個點i不需要傘，則疲勞值不變dp[i] = dp[i-1]。

如果前一個點i-1走到這一個點i需要傘，則從前面找一把傘。

即遍歷前面的每個點j，如果點j處有傘，dp[i] = min(dp[i], dp[j]+(i-j)*fig[j])。fig[j]意為第j個點出傘所需要的疲勞值。

代碼

#include <bits/stdc++.h> using namespace std; typedef long long ll; bool seg[2010]; //seg[i]=true表示從i-1走到i需要傘 int umb[2010]; //umb[i]如果不為INT_MAX表示第i個位置有傘，且umb[i]是這個點所有傘疲勞值的最小值 int dp[2010]; //dp[i]表示走到第i個點最少需要的疲勞值 int main(){ios::sync_with_stdio(false);int a,n,m;cin >> a >> n >> m;int k1,k2;//將seg[k1+1,k2]填充為true,邊界考慮清楚，注意seg后面的注釋 for(int i = 1;i <= n; ++i) cin >> k1 >> k2, fill(seg+k1+1,seg+k2+1,true);//umb表示傘 fill(umb, umb+2010, INT_MAX);for(int i = 1;i <= m; ++i) cin >> k1 >> k2, umb[k1] = min(umb[k1],k2);fill(dp+1, dp+2010, INT_MAX/2);for(int i = 1;i <= a; ++i){//如果從i-1走到i需要傘，則從前面找一把傘 if(seg[i]){for(int j = i-1;j >= 0; --j)if(umb[j] != INT_MAX)dp[i] = min(dp[i], dp[j]+(i-j)*umb[j]);}else //不需要傘，疲勞值不變 dp[i] = dp[i-1];}if(dp[a] == INT_MAX/2) dp[a] = -1;cout << dp[a] << endl;return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Codeforces 988F. Rain and Umbrellas的全部內容，希望文章能夠幫你解決所遇到的問題。

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