1624 取余最长路-白红宇

1624 取余最长路

阅读量：5262 次

发布时间：2019-06-14

本文共 2045 字，大约阅读时间需要 6 分钟。

时间限制：1 秒空间限制：131072 KB 分值: 40

佳佳有一个n*m的带权矩阵，她想从(1,1)出发走到(n,m)且只能往右往下移动，她能得到的娱乐值为所经过的位置的权的总和。

有一天，她被下了恶毒的诅咒，这个诅咒的作用是将她的娱乐值变为对p取模后的值，这让佳佳十分的不开心，因为她无法找到一条能使她得到最大娱乐值的路径了！

她发现这个问题实在是太困难了，既然这样，那就只在3*n的矩阵内进行游戏吧！

现在的问题是，在一个3*n的带权矩阵中，从(1,1)走到(3,n)，只能往右往下移动，问在模p意义下的移动过程中的权总和最大是多少。

样例解释：

移动的方案为“下下右”。

Input

单组测试数据第一行两个数n(1<=n<=100000),p(1<=p<=1000000000)。接下来3行，每行n个数，第i行第j列表示a[i][j]表示该点的权(0<=a[i][j]

Output

一个整数表示答案。

Input示例

2 32 22 20 1

Output示例

2 思路:二分；

我们可以发现所有可能的路径都可以由两个拐点决定，所以最终的和可以这样，sum=ans[3][n]-ans[3][y-1]+ans[2][y]-ans[2][x-1]+ans[1][x]; sum=((ans[3][n]-ans[3][y-1]+ans[2][y])%m+(ans[1][x]-ans[2][x-1])%m)%m; ans为每行的前缀和； 那么我们重小到大枚举y，然后将当前的（<=y）下标的(ans[1][x]-ans[2][x-1])%m)%m加入set，然后二分查找（m-ans[3][n]-ans[3][y-1]+ans[2][y])%m； 因为，set中的数<=m-1;并且按升序排列，我们在set中找m-(ans[3][n]-ans[3][y-1]+ans[2][y])%m这个的加上（ans[3][n]-ans[3][y-1]+ans[2][y]）再对m取余为0；是最小的 我们先来看，假设我们有一个数tt，在m的完全省余系中，我们要找一个和他之和对m取余为0的数，下面我们要证明这个数是唯一的，假设存在两个数和他和模m为0；（x1+tt）%m==(x2+tt)%m; 那么有x2-x1=km；由于-1

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
            
              7 #include
              8 #include
              
                9 #include
               
                10 using namespace std;11 typedef long long LL;12 LL ans[5][100005];13 set
                
                 G;14 set
                 
                  ::iterator it;15 int main(void)16 {17 int i,j,k;18 LL n,m;19 memset(ans,0,sizeof(ans));20 scanf("%lld %lld",&n,&m);21 for(i=1; i<=3; i++)22 {23 for(j=1; j<=n; j++)24 {25 scanf("%lld",&ans[i][j]);26 ans[i][j]+=ans[i][j-1];27 }28 }29 LL maxx=0;30 int flag=0;31 for(i=1; i<=n; i++)32 {33 LL sum=(ans[3][n]+ans[2][i]-ans[3][i-1])%m;34 LL nn=m-sum;35 nn=(nn%m+m)%m;36 G.insert(((ans[1][i]-ans[2][i-1])%m+m)%m);37 it=G.lower_bound(nn);38 if(it!=G.begin())39 it--;40 {41 LL ak=((*it+sum))%m;42 it=G.end();it--;43 LL uu=*it;44 LL sk=(uu+sum)%m;45 if(sk>ak)46 {47 ak=sk;48 49 }maxx=max(maxx,ak);50 }51 if(flag)52 break;53 }54 printf("%lld\n",maxx);55 return 0;56 }

转载于:https://www.cnblogs.com/zzuli2sjy/p/5477512.html

你可能感兴趣的文章