C. Pollywog
题目描述
原题题目链接. http://codeforces.com/contest/917/problem/C 题目大意为: 有 $x$ 只蝌蚪, 在 $n$ 个石头中的最左端的 $x$ 个石头上, 这 $n$ 个石头是在同一直线上的. 每一次只能最左边的一个蝌蚪进行跳跃, 并且只能跳 $1$ 至 $k$ 步, 跳 $i$ 步要花费 $c_i$ 的体力. 在蝌蚪跳跃时, 是不能跳到已有蝌蚪的石头上. 在这 $n$ 个石头里面有 $q$ 个石头是特殊的石头, 跳上这 $q$ 个石头中的第 $p$ 个要额外花费 $w_p$ 的体力值. 问当所有蝌蚪跳到最右边的 $x$ 个石头时的最小体力值.
思路
首先, 根据题意我们能知道所有的蝌蚪都一定在连续的 $k$ 块石头上. 现在进行一个小小的证明: 假设这些蝌蚪不在连续的 $k$ 块石头上, 则最左边的蝌蚪在跳跃时一定会跳在最右边的蝌蚪的左边, 不会使最右端点向右移动, 但是因为最左边的蝌蚪跳动了, 所以最左端点会向右移动, 这样的话, 区间就会缩短. 知道当最左边的蝌蚪和最右边的蝌蚪的距离小于 $k$ 时, 才能在向右跳跃时将最右端点向右移动, 又因为开始的时候所有的蝌蚪都在最左边的 $x$ 个石头上, 所以不会使区间大于 $k$.
因此我们就可以处理出来长度为 $k$ 的所有的情况之间的转移. 我们定义一个单位元矩阵,$num[i][j]$ 表示状态为 $i$ 的石头转移成为状态为 $j$ 的石头的花费. 什么是状态为 $i$ 的石头呢??? 我们将 $i$ 转成二进制, 这样我们就得到了一个 $01$ 串, 在这个 $01$ 串中,$0$ 表示这个石头上没有蝌蚪, 反之 $1$ 表示有蝌蚪. 因为我们一共就只需要枚举 $k$ 块石头, 并且只有 $x$ 只青蛙, 且 $k,x \le 8$, 所以最多就只有 $C_8^4$ 种情况, 将二进制串离散一下就好了. 这就是预处理.
我们得到了一个转移的邻接矩阵, 我们就可以用这个矩阵来进行矩乘, 先不考虑特殊的石头, 所以就计算这个矩阵的 $n-x$ 次幂就可以,$n-x$ 次幂的意思是, 每一次都将当前 $k$ 块石头向右进行移动一块石头, 这样移动 $n-x$ 次就是答案, 但是特殊的石头要更改答案, 所以我们到达一块特殊的石头, 就停下来暴力就可以了. 我们知道一块特殊的石头只能对 $k$ 个转移带来影响. 所以我们暴力停下来转移是可以的, 时间复杂的是 $O(k^2 \times q \times C_k^x)$.
代码
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- #define inf 1e18
- #define N 10
- int x,k,n,q,cnt;long long num[N];int bel[1<<10];
- struct Square
- {
- long long num[71][71];
- Square()
- {for(int i=1;i<=70;i++) {for(int j=1;j<=70;j++) num[i][j]=inf;num[i][i]=0;}}
- Square operator * (const Square &a) const
- {
- Square tmp;
- for(int i=1;i<=cnt;i++)
- tmp.num[i][i]=inf;
- for(int i=1;i<=cnt;i++)
- for(int j=1;j<=cnt;j++)
- for(int k=1;k<=cnt;k++)
- tmp.num[i][j]=min(tmp.num[i][j],num[i][k]+a.num[k][j]);
- return tmp;
- }
- Square operator ^ (const int &x)
- {
- if(!x) return Square();
- Square tmp,tmp1;int times=x;
- for(int i=1;i<=cnt;i++)
- for(int j=1;j<=cnt;j++) tmp1.num[i][j]=num[i][j];
- while(times) {if(times&1) tmp=tmp*tmp1;times>>=1;tmp1=tmp1*tmp1;}
- return tmp;
- }
- }one;
- struct Stone
- {int place;long long val;}stone[30];
- bool calc(int tmp)
- {
- int many=0;
- for(int i=1;i<=8;i++) if(tmp&(1<<(i-1))) many++;
- return many==x;
- }
- bool cmp(const Stone &a,const Stone &b)
- {return a.place<b.place;}
- int main()
- {
- scanf("%d%d%d%d",&x,&k,&n,&q);
- for(int i=0;i<=(1<<k)-1;i++) if(calc(i)) bel[i]=++cnt;
- for(int i=1;i<=k;i++) scanf("%lld",&num[i]);
- for(int i=1;i<=q;i++) scanf("%d%lld",&stone[i].place,&stone[i].val);
- sort(stone+1,stone+q+1,cmp);
- for(int i=1;i<=cnt;i++) one.num[i][i]=inf;
- for(int i=1;i<=(1<<k)-1;i++)
- {
- if(!bel[i]) continue;
- if(i&1)
- {for(int j=1;j<=k;j++)
- {if(!((1<<j)&i)) one.num[bel[i]][bel[((1<<j)|i)>>1]]=num[j];}}
- else one.num[bel[i]][bel[i>>1]]=0;
- }
- int now=1;long long sum=0;Square ans;
- for(int i=1;i<=q;i++)
- {
- if(stone[i].place>n-x) {sum+=stone[i].val;continue;}
- ans=ans*(one^(stone[i].place-now)),now=stone[i].place;
- for(int j=1;j<=(1<<k)-1;j+=2)
- if(bel[j])
- for(int k=1;k<=cnt;k++)
- ans.num[k][bel[j]]+=stone[i].val;
- }
- ans=ans*(one^(n-x+1-now));
- printf("%lld",ans.num[1][1]+sum);
- }
来源: https://www.cnblogs.com/yangsongyi/p/9775609.html