A. 矩阵取数游戏

题意

​    给定一个 $n\times m$ 的矩阵,其中每个元素为非负整数。每次你可以从每行的行首或行末取一个元素,得到的分数为当前元素的值 $a_{ij}\times 2^k$ ,$k$ 为当前是第几次取该行上的元素。 问最大得分为多少。

思路

​    首先我们发现,虽然答案问的是 $n$ 行,但是我们发现,不同行之间是不会相互影响的,我们只需要讨论一行的情况,然后对每行都处理一遍就可以了。
​    那么对于一行上的 $m$ 个元素,我们每一次取都有两种选择,一个是取行首,一个是取行尾。我们发现这是一个区间问题,对于区间 $[i,j]$ 的最优情况,我们可以从 $[i+1,j]$ 和 $[i,j-1]$ 这两个的最优情况转移过来,因此我们可以定义 $f[i][j]$ 是从第 $i$ 个元素到第 $j$ 的元素得分的最大值,然后从上述两个状态转移过来。
​    还有一个问题就是我们的 $2^k$ 问题,我们考虑到大区间的最优值是从小区间转移来,也就是说小区间乘的指数高,大区间乘的指数低,我们又是从小区间推到大区间,转移一次就乘一次,最后肯定是大区间的少,小区间的多了。qwq因为这个题的次数可能很高,会爆long long,实在是不想写高精度,就用了__int128,第一次用,感觉还不错QAQ..

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=85;
int n,m;
__int128 map[maxn][maxn];
__int128 dp[maxn][maxn],ans;
void read(__int128 &x)
{
    x=0;
    char ch;
    ch=getchar();
    while(ch<'0'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
}
void out(__int128 x)
{
    if(x>=10) out(x/10);
    putchar(x%10+'0');
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) read(map[i][j]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int f=1;f<=m;f++)
        {
            for(int j=1;j<=m;j++) dp[f][j]=0;
        }
        for(int len=1;len<=m;len++)
        {
            for(int j=1;j+len-1<=m;j++)
            {
                int k=j+len-1;
                dp[j][k]=max(dp[j+1][k]*2+map[i][j]*2,dp[j][k-1]*2+map[i][k]*2);
            }
        }
        ans+=dp[1][m];
    }
    out(ans);
    return 0;
}


B. 关路灯

题意

​    在一条街道上有 $n$ 个路灯开着,他们可以看作分布在 $x$ 轴上,每个路灯有一定的坐标,也就是代表他们的位置。每个路灯也有一定的功率 $x$ ,代表一秒钟消耗多少电能。姜大佬初始位置在 $c$ ,他每天早晨出来关掉路灯。它可以先关左边的也可以先关右边的,他的行走速率是 $1m/s$ ,问最少消耗多少电能能关掉所有路灯。

思路

​    又是一道区间dp的题,那么我们可以思考一下,首先小姜老师肯定不能跳着关路灯,也就是说这个区间内中间的路灯都被关闭了,他会关一个区间的左端点或者右端点,而不会关这个区间外面的。那么我们就可以枚举区间长度来解决这个问题,从小的枚举到大的。
​    那么我们思考一下如何定义这个状态。我们可以定义关闭区间 $[i,j]$ 的路灯,最少消耗电能为 $f[i][j]$ ,如果需要转移状态的话,我们想到,对于一个方向,小姜老师可以继续往前走,关掉前面那盏灯,也可以返回去,关闭它屁股后面那盏灯。因为是有两个方向的,所以我们可以拓宽一维,用 $f[i][j][0/1]$ 来表示小姜老师现在是在往左走还是往右走,那么很明显 $f[i][j][0]$ 这个状态可以从 $f[i+1][j][0/1]$ 来转移分别对应着小姜老师继续往前走关眼前的,和返回关屁股后的。相应的 $f[i][j][1]$ 就可以从 $f[i][j-1][0/1]$ ,转移的时候再加上消耗的电能即可!

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=55;
const int inf=100000000;
int n,c;
int lt[maxn]; //lantern pos
int en[maxn]; //energy 
int sum[maxn]; //prefix sum
int dp[maxn][maxn][2];
int calc(int i,int j)
{
    return sum[n]-(sum[j]-sum[i-1]);
}
int main()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<=1;k++) dp[i][j][k]=inf;
        }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&lt[i],&en[i]);
        sum[i]=en[i]+sum[i-1];
    }
    dp[c][c][0]=dp[c][c][1]=0;
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            dp[i][j][0]=min(dp[i+1][j][0]+(lt[i+1]-lt[i])*calc(i+1,j),dp[i+1][j][1]+(lt[j]-lt[i])*calc(i+1,j));
            dp[i][j][1]=min(dp[i][j-1][0]+(lt[j]-lt[i])*calc(i,j-1),dp[i][j-1][1]+(lt[j]-lt[j-1])*calc(i,j-1));
        }
    }
    printf("%d",min(dp[1][n][0],dp[1][n][1]));
    return 0;
}


C. 小a和uim之大逃离

题意

​    给定一个 $n\times m$ 的矩阵,每个格子中有 $0\sim k$ 滴魔液,小姜老师和它朋友可以从任意地点开始,一起向右或者向下走,他们每个人有一个容量为 $k$ 的瓶子,由小姜老师开始轮流收集地上的魔液,当收集魔液大于 $k$ 的时候,会对 $k+1$ 取模,问他们有多少种方法使得收集的魔液数量相同。

思路

​    很显然我们可以写一个5维dp,用 $f[i][j][p][l][0/1]$ 来表示,当到了坐标为 $(i,j)$ 的格子的时候,小姜老师拥有魔液 $p$ 滴,他的朋友拥有魔液 $l$ 滴,并且这一次是由小姜老师采集的/由他的朋友采集的。这样的话,感觉比较好些,但是。。空间占用非常的高,我们优化一下,因为问的是收集相等,所以只需要维护他们的差就可以了,也就是说,只需要将 $(p-l+k)\\%k$ 维护一下就可以了,因此循环枚举坐标以及他们的差,从低的向高的转移就可以了。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=805;
int map[maxn][maxn];
int dp[maxn][maxn][16][2];
const int mod=1e9+7;
int n,m,k;
long long ans;
int main()
{
//    freopen("test.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    k++;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            dp[i][j][map[i][j]%k][0]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int t=1;t<=k;t++)
            {
                dp[i][j][t%k][0]+=dp[i-1][j][(t-map[i][j]+k)%k][1];dp[i][j][t%k][0]%=mod;
                dp[i][j][t%k][0]+=dp[i][j-1][(t-map[i][j]+k)%k][1];dp[i][j][t%k][0]%=mod;
                dp[i][j][t%k][1]+=dp[i-1][j][(t+map[i][j])%k][0];dp[i][j][t%k][1]%=mod;
                dp[i][j][t%k][1]+=dp[i][j-1][(t+map[i][j])%k][0];dp[i][j][t%k][1]%=mod;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ans+=dp[i][j][0][1]%mod;
            ans%=mod;
        }
    }
    printf("%lld",ans);
}
最后修改:2020 年 08 月 18 日 01 : 02 AM
如果觉得我的文章对你有用,请随意赞赏