Simple Operations on Sequence

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以内就考虑状压或者搜索，搜索毫无头绪可言，故考虑状压。状压在本题很有技巧性

设 i状态为当前归位元素状态，1为归位。

1011 代表将 a4 a2 a1放在 b3 b2 b1时的状态。至于先放哪一个在b1 ,我们通过二进制枚举都能够枚举到，我们只需要将目前要放的放在下一个b就能够满足。

以1有0个的情况为例，也就是我们要从0扩展一个的情况，枚举全部n个，得到了答案，但消耗的y我们并没有算进去。

n=4为例

 最开始我们把a2置换到b1位置为例， 我们此时y=0,仅计算了消耗x的代价

置换我们又要把 一个数置换到b2位置，

如果是a1,我们发现它前面有个2，所以y=1  。然后一次类推，结果竟然与最终置换次数一模一样。那是因为1次置换改变了一次逆序数，两次不相同的置换，又会改变一次逆序数，

 1  2   3  4  5 为例

置换 2 3  

 1   3  2   4 5 逆序数加1

置换 1 3

 3 1 2 4 5 逆序数加1 

置换 4 2

3 1 4 2 5 逆序数又加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));
            }
            else
                temp++;
        }
    }

    cout<<dp[(1<<n)-1];

}