迟到一天的题解QAQ

http://codeforces.com/contest/917/problem/C

题意:x个青蛙

每次让最左边的青蛙往前跳1~k步,不允许两只青蛙呆在同一个格子上

跳1~k格消耗c₁~c_k的体力

有q个特殊的点,第p个点每只青蛙跳上去会消耗额外的w_p点体力(如果是负数那么就是增加体力)

一个长度为x的一条路(一共x个格子的路)

一开始x个青蛙在1,2...x的位置

问到达n-x+1,n-x+2....n的位置

最少需要多少体力(可以为负)

1<=x<=k<=8 n<=1e8 0<=q<=25 (q<=n-k)

思路:

感谢@FizzyDavid提供的题解

这个东西,首先想到dp

dp[i][j]表示 第一只青蛙在i,后续青蛙相对位置为j(因为最多跳k格所以j<2^k也就是2^8)

然后这个dp暴力转移是O(2^8 n*8)的,显然不可以

就算有别的转移姿势,也不太行

但是以往遇到相似的题我们会想矩阵乘法对吧

矩阵乘法的一个问题是只能转移一格,而这里i,"101"选k=3就跳成了i+2,"110"

当然我们可以考虑用i+1,"011"做过渡;换句话说我们定义

dp[i][j]表示,在第i个位置,后面j个位置青蛙相对位置为j

这个题的dp.....也有点相似于矩阵乘法对吧...

我们定义新的乘法,那么如果这个乘法也满足结合律,那么我们就可以用同样的矩阵乘法来做

虽然我不会证,但是FizzyDavid告诉我是对的(大雾)

转移方式是

新的矩阵C(i,k) = Min{A(i,j)+B(j,k)}

我觉得好像结合律其实挺对的,你在前A步到达某个点,消耗是多少

然后再走B步,那么我们枚举在第A步的状态就行

那么代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int c[15];
int ma[305];
int cnt=0;
const long long inf=1999999999999999999ll;
struct matrix
{
    long long a[75][75];
    friend matrix operator * (const matrix &a,const matrix &b)
    {
        int i,j,k;
        matrix c;
        for (i=0;i<cnt;i++)
        {
            for (j=0;j<cnt;j++)
            {
                c.a[i][j]=inf;
            }
        }
        for (i=0;i<cnt;i++)
        {
            for (j=0;j<cnt;j++)
            {
                for (k=0;k<cnt;k++)
                {
                    c.a[i][k]=min(c.a[i][k],a.a[i][j]+b.a[j][k]);
                }
            }
        }
        return c;
    }
    matrix ()
    {
        int i;
        int j;
        for (i=0;i<75;i++)
        {
            for (j=0;j<75;j++)
            {
                a[i][j]=inf;
            }
            a[i][i]=0;
        }
    }
};
matrix a;
matrix mul(int x)
{
    if (x==0) return matrix();
    matrix b=mul(x/2);
    b=b*b;
    if (x%2==1) b=b*a;
    return b;
}
pair<int,int> p[75];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int x,k;
    int n,q;
    scanf("%d%d%d%d",&x,&k,&n,&q);
    int i;
    for (i=0;i<k;i++)
    {
        scanf("%d",&c[i]);
    }
    memset(ma,-1,sizeof(ma));
    for (i=0;i<(1<<k);i++)
    {
        int j;
        int sum=0;
        for (j=0;j<k;j++)
        {
            if ((1<<j)&i) sum++;
        }
        if (sum==x) ma[i]=cnt++;
    }
    int j;
    for (i=0;i<cnt;i++)
    {
        for (j=0;j<cnt;j++)
        {
            a.a[i][j]=inf;
        }
    }
    for (i=0;i<(1<<k);i++)
    {
        if (ma[i]==-1) continue;
        if (i&1)
        {
            //Can move!
            for (j=1;j<=k;j++)
            {
                if ((1<<j)&i) continue;
                a.a[ma[i]][ma[((1<<j)^i)>>1]]=c[j-1];
            }
        }
        else
        {
            a.a[ma[i]][ma[i>>1]]=0;
        }
    }
    int now=1;
    for (i=0;i<q;i++)
    {
        scanf("%d%d",&p[i].first,&p[i].second);
    }
    sort(p,p+q);
    matrix xx;
    long long ans=0;
    for (i=0;i<q;i++)
    {
        if (p[i].first>=n-x+1)
        {
            ans+=p[i].second;
            continue;
        }
        xx=xx*mul(p[i].first-now);
        now=p[i].first;
        int j;
        for (j=1;j<(1<<k);j+=2)
        {
            if (ma[j]!=-1)
            {
                int l;
                for (l=0;l<cnt;l++)
                {
                    xx.a[l][ma[j]]+=p[i].second;
                }
            }
        }
    }
    xx=xx*mul(n-x+1-now);
    cout<<xx.a[0][0]+ans<<endl;
    return 0;
}