傳送門

文章目錄

• 題意：
• 思路：

題意：

給你$n$個(gè)點(diǎn)，從$i$到$j$的花費(fèi)是$max(c_i,a_j?a_i)$，求從$1$開(kāi)始經(jīng)過(guò)每個(gè)點(diǎn)再回到$1$的最小花費(fèi)。

思路：

首先可以發(fā)現(xiàn)我們的起點(diǎn)在哪里是一樣的，只需要走出一個(gè)環(huán)來(lái)就行。讓后由于花費(fèi)是$max(c_i,a_j?a_i)$，所以我們至少要花費(fèi)$c_i$，最終的花費(fèi)一定$>={\sum }_{i=1}^n{c}_i$，所以我們將$c_i$減去，即花費(fèi)變成$max(0,a_j?a_i?c_i)$，觀察可知當(dāng)從大的$a_i$到小的$a_j$的時(shí)候，花費(fèi)一定是$0$，所以我們按照$a$從小到大排序，這樣到最后一個(gè)點(diǎn)的時(shí)候回退到?jīng)]有走過(guò)的點(diǎn)花費(fèi)是$0$，我們只需要確定從$1$開(kāi)始走的最小花費(fèi)即可，也就是讓$a_i+c_i$最大，所以對(duì)于每個(gè)$i$，我們都從$ma{x}_{j<i}(a_j+c_j)$轉(zhuǎn)移過(guò)來(lái)就好啦，不能轉(zhuǎn)移的就相當(dāng)于沒(méi)走，當(dāng)?shù)阶詈笠粋€(gè)點(diǎn)的時(shí)候往后免費(fèi)回退即可。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; PII p[N]; LL ans;int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&p[i].X,&p[i].Y),ans+=p[i].Y;sort(p+1,p+1+n);LL mx=p[1].X+p[1].Y;for(int i=2;i<=n;i++){ans+=max(0ll,p[i].X-mx);mx=max(mx,1ll*p[i].X+p[i].Y);}printf("%lld\n",ans);return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #712 (Div. 2) E. Travelling Salesman Problem 思维转换的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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