C. Pollywog

题目描述

　　原题题目链接。题目大意为：有$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);

}

巴特西

CF917C Pollywog —— 状压DP + 矩乘优化

C. Pollywog

题目描述

思路

代码

最新文章

热门文章