傳送門
題意
有 n 個機器人，每個機器人會讀入一個 x ，并回傳 ax+b ，
現在銀臨姐姐手里有一個數 x ，她想將機器人按某種順序排列，使得最侄訓傳得到的 x 盡可能大，
對于所有的資料，1 ≤ n , x , a i , b i ≤ 20 \le n,x,a_i,b_i\le20 ≤n,x,ai?,bi?≤20 ，
分析
狀壓dp裸題：
f
[
i
]
f[i]
f[i]表示狀態為
i
i
i(i中第j位為0表示還沒用過第j個機器人，為1時表示已經用過了第j個機器人，j=[0~n-1])時，結果的最大值，
狀態更新舉例：
f
[
(
111
)
2
]
f[(111)_2]
f[(111)2?]要從
f
[
(
011
)
2
]
,
f
[
(
101
)
2
]
,
f
[
(
110
)
2
]
f[(011)_2],f[(101)_2],f[(110)_2]
f[(011)2?],f[(101)2?],f[(110)2?]三個狀態更新過來，
f
[
(
111
)
2
]
=
m
a
x
(
a
[
2
]
?
f
[
(
011
)
2
]
+
b
[
2
]
,
a
[
1
]
?
f
[
(
101
)
2
]
+
b
[
1
]
,
a
[
0
]
?
f
[
(
110
)
2
]
+
b
[
0
]
)
f[(111)_2]=max(a[2]*f[(011)_2]+b[2],a[1]*f[(101)_2]+b[1],a[0]*f[(110)_2]+b[0])
f[(111)2?]=max(a[2]?f[(011)2?]+b[2],a[1]?f[(101)2?]+b[1],a[0]?f[(110)2?]+b[0])
最終答案就是
f
[
(
1111...11
)
2
]
f[(1111...11)_2]
f[(1111...11)2?](n個1)
但是動手算算上界會超longlong，
調了好久的高精都有問題（板子是很久之前寫的，現在看起來當時寫的并不好），最后__int128水過去了，
關于__int128
仔細整理一下__int128，還挺好用的，我電腦上可以正常使用，不存在網上說的Linux才能用，
但是：
1.__int128的上界是3.4e38，太大了還是不行，
2.要手動實作輸入輸出函式，
3.位運算的時候要注意寫法（被坑過），
代碼
#include <bits/stdc++.h>
using namespace std;
//-----pre_def----
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)
//---------------
const int N = 23;
int n, x;
int a[N], b[N];
__int128 f[1 << 21];
inline void print(__int128 x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int StartTime = clock();
#endif
scanf("%d%d", &n, &x);
f[0] = x;
fir(i, 0, n - 1)
{
scanf("%d%d", &a[i], &b[i]);
}
for (int i = 1; i <= (1 << n) - 1; i++)
{
for (int j = 0; j < n; j++)
{
if ((i >> j) & 1)
{
f[i] = max(f[i], f[i - (1 << j)] * a[j] + b[j]);
}
}
}
print(f[(1 << n) - 1]);
#ifndef ONLINE_JUDGE
printf("Run_Time = %d ms\n", clock() - StartTime);
#endif
return 0;
}
一道相似的高精+dp題目
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263727.html
標籤：其他