做任务送科比网站,做网站 斗地主,网站建设一般多少钱网址,东莞网站优化费用CF917C. Pollywog
题目描述
Solution
看完题#xff0c;基本的方向就是状压DP。
因为每次都是最左边的青蛙跳至多kkk步#xff0c;容易发现任意两个青蛙之间的距离始终小于kkk。
因此可以把连续kkk个位置的空闲状态压在(kx)≤70\binom{k}{x}\leq70(xk)≤70个二进制数中…CF917C. Pollywog
题目描述
Solution
看完题基本的方向就是状压DP。
因为每次都是最左边的青蛙跳至多kkk步容易发现任意两个青蛙之间的距离始终小于kkk。
因此可以把连续kkk个位置的空闲状态压在(kx)≤70\binom{k}{x}\leq70(xk)≤70个二进制数中用f[i][j]f[i][j]f[i][j]表示i...ik−1i...ik-1i...ik−1的青蛙存在状态为jjj的最小代价并保证iii位置有青蛙避免冗余的重复状态这样转移的时候就枚举iii位置的青蛙跳几步ttt并把j′(jxor1)or2tj(j\;xor\;1)\;or\;2^t\;j′(jxor1)or2t不断右移保证第一个位置是111设移了ppp位便从f[i][j]f[i][j]f[i][j]转移至f[ip1][j′p]f[ip1][jp]f[ip1][j′p]。
这样的时间复杂度是O(nk(kx))O(nk\binom{k}{x})O(nk(xk))的看似是一个很不错的跳板但事实上这种方法及其误导我在这里卡了一万年雾 事实上我们不需要用上述方法避免状态冗余只需要在第iii个位置上没青蛙即((jand1)0)((j\;and\;1)0)((jand1)0)时的转移变为f[i][j]−f[i1][j1]f[i][j]-f[i1][j1]f[i][j]−f[i1][j1]。那么就不用计算所谓的ppp了可以直接实现从f[i][j]−f[i1][j′]f[i][j]-f[i1][j]f[i][j]−f[i1][j′]的转移。
这样我们每次的转移都是从i−i1i-i1i−i1的可以用矩乘优化。
对于特殊的位置iii用矩乘算到f[i][...]f[i][...]f[i][...]之后暴力枚举转移加额外贡献然后继续矩乘转移即可。
时间复杂度O((kx)3lgnq(kx)2)O(\binom{k}{x}^3\lg nq\binom{k}{x}^2)O((xk)3lgnq(xk)2)
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int MAXN600005;
const ll INF1ll60;
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int c[10],id[305],to[305],cnt0;
PR p[105];
struct Matrix
{int n;ll A[71][71];Matrix(int n170) { nn1; for (int i1;in;i)for (int j1;jn;j) A[i][j](ij?0:INF);}Matrix operator * (Matrix b){Matrix ans;for (int i1;in;i) ans.A[i][i]INF;for (int k1;kn;k)for (int i1;in;i)for (int j1;jn;j) upmin(ans.A[i][j],A[i][k]b.A[k][j]);return ans;} Matrix operator ^ (int y){if (!y) return Matrix();Matrix ret*this,ans;for (;y;y1){if (y1) ansans*ret;retret*ret;}return ans;}
} nxt,ans;
int main()
{int xread(),kread(),nread(),qread();for (int i1;ik;i) c[i]read();for (int i1;iq;i) p[i].firead(),p[i].seread();sort(p1,pq1);for (int i1;i1k;i) if (__builtin_popcount(i)x) id[i]cnt,to[cnt]i;for (int i1;icnt;i){for (int j1;jcnt;j) nxt.A[i][j]INF;if (!(to[i]1)) { nxt.A[i][id[to[i]1]]0; continue; }for (int j1;jk;j){if ((to[i]j)1) continue;nxt.A[i][id[(to[i]|(1j))1]]c[j];}}ll sum0; int now1;for (int i1;iq;i){if (p[i].fin-x) { sump[i].se; continue; }ansans*(nxt^(p[i].fi-now)),nowp[i].fi;for (int j1;j1k;j2)if (id[j])for (int t1;tcnt;t) ans.A[t][id[j]]p[i].se;}ansans*(nxt^(n-x1-now));printf(%lld\n,ans.A[1][1]sum);return 0;
}
