F - Simple Operations on Sequence?Editorial

?/?

---

Time Limit: 2 sec / Memory Limit: 1024 MB

Score :?500500?points

Problem Statement

Given are two sequences of?NN?integers each:?A = (A_1, A_2, \ldots, A_N)A=(A1?,A2?,…,AN?)?and?B = (B_1, B_2 \ldots, B_N)B=(B1?,B2?…,BN?).

On the sequence?AA, you can do the two operations below any number of times (possibly zero) in any order.

• Choose an integer?ii?satisfying?1 \leq i \leq N1≤i≤N, and increase or decrease?A_iAi??by?11, for the cost of?XX?yen (Japanese currency).
• Choose an integer?ii?satisfying?1 \leq i \leq N-11≤i≤N?1, and swap the values of?A_iAi??and?A_{i+1}Ai+1?, for the cost of?YY?yen.

Print the minimum total cost needed to make the sequence?AA?equal the sequence?BB?by repeating the above.

Constraints

• 2 \leq N \leq 182≤N≤18
• 1 \leq X \leq 10^81≤X≤108
• 1 \leq Y \leq 10^{16}1≤Y≤1016
• 1 \leq A_i, B_i \leq 10^81≤Ai?,Bi?≤108
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

NN XX YY A_1A1? A_2A2? \ldots… A_NAN? B_1B1? B_2B2? \ldots… B_NBN?

Output

Print the minimum total cost needed to make?AA?equal?BB.

---

Sample Input 1?Copy

Copy

4 3 5 4 2 5 2 6 4 2 1

Sample Output 1?Copy

Copy

16

Initialy, we have?A = (4, 2, 5, 2)A=(4,2,5,2).
The following sequence of operations makes?AA?equal?BB.

• Pay?X = 3X=3?yen to increase the value of?A_3A3??by?11, making?A = (4, 2, 6, 2)A=(4,2,6,2).
• Pay?Y = 5Y=5?yen to swap the values of?A_2A2??and?A_3A3?, making?A = (4, 6, 2, 2)A=(4,6,2,2).
• Pay?Y = 5Y=5?yen to swap the values of?A_1A1??and?A_2A2?, making?A = (6, 4, 2, 2)A=(6,4,2,2).
• Pay?X = 3X=3?yen to decrease the value of?A_4A4??by?11, making?A = (6, 4, 2, 1)A=(6,4,2,1).

The total cost of these operations is?3+5+5+3 = 163+5+5+3=16?yen, which is the minimum possible.

---

Sample Input 2?Copy

Copy

5 12345 6789 1 2 3 4 5 1 2 3 4 5

Sample Output 2?Copy

Copy

0

AA?and?BB?are equal from the beginning, so no operation is needed.

---

Sample Input 3?Copy

Copy

18 20719114 5117250357733867 10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712 14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

Sample Output 3?Copy

Copy

13104119429316474

Note that values in input or output may not fit into?3232-bit integer types.

=========================================================================

20以內(nèi)就考慮狀壓或者搜索，搜索毫無(wú)頭緒可言，故考慮狀壓。狀壓在本題很有技巧性

設(shè) i狀態(tài)為當(dāng)前歸位元素狀態(tài)，1為歸位。

1011 代表將 a4 a2 a1放在 b3 b2 b1時(shí)的狀態(tài)。至于先放哪一個(gè)在b1 ,我們通過(guò)二進(jìn)制枚舉都能夠枚舉到，我們只需要將目前要放的放在下一個(gè)b就能夠滿足。

以1有0個(gè)的情況為例，也就是我們要從0擴(kuò)展一個(gè)的情況，枚舉全部n個(gè)，得到了答案，但消耗的y我們并沒(méi)有算進(jìn)去。

n=4為例

?最開(kāi)始我們把a(bǔ)2置換到b1位置為例， 我們此時(shí)y=0,僅計(jì)算了消耗x的代價(jià)

置換我們又要把 一個(gè)數(shù)置換到b2位置，

如果是a1,我們發(fā)現(xiàn)它前面有個(gè)2，所以y=1? 。然后一次類推，結(jié)果竟然與最終置換次數(shù)一模一樣。那是因?yàn)?次置換改變了一次逆序數(shù)，兩次不相同的置換，又會(huì)改變一次逆序數(shù)，

?1? 2? ?3? 4? 5 為例

置換 2 3??

?1? ?3? 2? ?4 5 逆序數(shù)加1

置換 1 3

?3 1 2 4 5 逆序數(shù)加1?

置換 4 2

3 1 4 2 5 逆序數(shù)又加1

#include <bits/stdc++.h> using namespace std;typedef long long int ll;const int N=(1<<18)+10;ll dp[N];ll a[20],b[20]; int get(int x){int ans=0;for(int i=0;(1<<i)<=x;i++){if(((1<<i)&x))ans++;}return ans;} int main() {int n;cin>>n;ll x,y;cin>>x>>y;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n;i++){cin>>b[i];}dp[0]=0;for(int i=1;i<(1<<n);i++){dp[i]=1e18;}for(int i=0;i<(1<<n);i++){int cnt=get(i);int temp=0;for(int j=n-1;j>=0;j--){if((i&(1<<j))==0){dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+x*abs(a[j]-b[cnt])+y*(temp));}elsetemp++;}}cout<<dp[(1<<n)-1];}

總結(jié)

以上是生活随笔為你收集整理的Simple Operations on Sequence的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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