文章目錄

• title
• solution
• code

title

solution

令$Magic=V_i\times V_j\times V_k...$
這里對$\sqrt[c]{Magic}$有一個很巧妙的轉換——取對數
$$\sqrt[c]{Magic}=(Magic{)}^{\frac{1}{c}}=e^{lo{g}_e(Magic{)}^{\frac{1}{c}}}$$$$lo{g}_{e}Magi{c}^{\frac{1}{c}}=\frac{1}{c}lo{g}_{e}Magic=\frac{1}{c}lo{g}_e(V_i\times V_j\times V_k...)$$$$=\frac{1}{c}\times (lo{g}_e{V}_i+lo{g}_e{V}_j+lo{g}_e{V}_k...)$$
于是就成功把神力值的相乘開方變為了相加
$(\frac{lo{g}_e{V}_i+lo{g}_e{V}_j+lo{g}_e{V}_k...}{c}{)}_{max}$👉這個獅子到這一步就長得很像0/1分數規劃問題了
實際上ta就似

考慮直接二分最后的答案
然后對咒語建$AC$自動機，在自動機上跑$0/1$分數規劃$DP$，判斷答案的大小
建$fail$指針時，順路把從根節點到$now$節點這一條串包含的咒語的信息進行類似前綴和的處理

設$dp[i][j]：$表示僅考慮前$i$個寶石，現在指向自動機上的$j$節點時的最大神力值
由$i$個寶石要轉移到$i+1$，就要看$i$寶石究竟長什么模樣
①：殘缺寶石，這個時候需要對始終可能都進行轉移
②：完整寶石，是什么就轉移什么
$to:$ $i$轉移$i+1$后$j$指向自動機上的節點
$$dp[i+1][to]=max(dp[i][j]+val[to])$$

code

#include <cmath> #include <queue> #include <cstdio> #include <cstring> using namespace std; #define inf 1e18 #define maxn 1600 #define eps 1e-7 int n, m, tot; queue < int > q; char s[maxn], T[maxn], path[maxn]; int sum[maxn], fail[maxn]; double val[maxn]; int trie[maxn][15]; double dp[maxn][maxn]; int g[maxn][maxn][2];void insert( double v ) {int now = 0, len = strlen( s );for( int i = 0;i < len;i ++ ) {int to = s[i] - '0';if( ! trie[now][to] ) trie[now][to] = ++ tot;now = trie[now][to];}sum[now] ++, val[now] += v; }void Fail() {while( ! q.empty() ) q.pop();fail[0] = 0;for( int i = 0;i < 10;i ++ )if( trie[0][i] ) {fail[trie[0][i]] = 0;q.push( trie[0][i] );}while( ! q.empty() ) {int now = q.front(); q.pop();sum[now] += sum[fail[now]];val[now] += val[fail[now]];for( int i = 0;i < 10;i ++ ) {if( trie[now][i] ) {fail[trie[now][i]] = trie[fail[now]][i];q.push( trie[now][i] );}elsetrie[now][i] = trie[fail[now]][i];}} }double DP( double x ) {for( int i = 0;i <= n;i ++ )for( int j = 0;j <= tot;j ++ )dp[i][j] = -inf;for( int i = 0;i <= tot;i ++ ) val[i] -= sum[i] * x;dp[0][0] = 0;for( int i = 0;i < n;i ++ ) { //前i個字符for( int j = 0;j <= tot;j ++ ) { //現在在AC自動機上的j節點if( dp[i][j] <= -inf ) continue; //dp[i][j]:最大魔術值for( int k = 0;k < 10;k ++ ) if( T[i] == '.' || T[i] == k + '0' ) {int to = trie[j][k];if( dp[i + 1][to] < dp[i][j] + val[to] ) {dp[i + 1][to] = dp[i][j] + val[to];g[i + 1][to][0] = j, g[i + 1][to][1] = k;//0:記錄點 1:記錄邊的字符 后面還原路徑用}}}}for( int i = 0;i <= tot;i ++ ) val[i] += sum[i] * x;int ans = 0;for( int i = 0;i <= tot;i ++ )if( dp[n][i] > dp[n][ans] ) ans = i;int pos = ans;for( int i = n;i;i -- )path[i] = g[i][pos][1] + '0', pos = g[i][pos][0];return dp[n][ans]; }int main() {scanf( "%d %d %s", &n, &m, T );for( int i = 1, v;i <= m;i ++ ) {scanf( "%s %d", s, &v );insert( log( v ) );}Fail();double l = 0, r = 1e9, ans;while( r - l > eps ) {double mid = ( l + r ) / 2;if( DP( mid ) > 0 ) ans = mid, l = mid;else r = mid;}DP( ans );printf( "%s", path + 1 );return 0; }

總結

以上是生活随笔為你收集整理的「BJOI2019」奥术神杖（AC自动机+DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

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