1624 取余最长路(set)

1624 取余最长路

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

佳佳有一个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]<p)。

Output

一个整数表示答案。

Input示例

2 3

2 2

0 1

Output示例

//以前竟然都没遇到过，set中竟然也有lower_bound(x) ,可以返回最小的大于等于 x 的迭代器

iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。

先码住，这题，很容易想到 N^2 解法，然而只需要枚举其中一个拐点即可，另一部分二分得出

 # include <cstdio>

 # include <cstring>

 # include <cstdlib>

 # include <iostream>

 # include <vector>

 # include <queue>

 # include <stack>

 # include <map>

 # include <bitset>

 # include <sstream>

 # include <set>

 # include <cmath>

 # include <algorithm>

 using namespace std;

 # define LL          long long

 # define pr          pair

 # define mkp         make_pair

 # define lowbit(x)   ((x)&(-x))

 # define PI          acos(-1.0)

 # define INF         0x3f3f3f3f3f3f3f3f

 # define eps         1e-

 # define MOD         

 inline LL scan() {

     LL x=,f=; char ch=getchar();

     while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 inline void Out(int a) {

     if(a<) {putchar('-'); a=-a;}

     if(a>=) Out(a/);

     putchar(a%+'');

 }

 # define MX

 /**************************/

 int n,p;

 LL sum[][MX];

 int main()

 {

     n=scan(); p=scan();

     for (int i=;i<;i++)

     {

         for (int j=;j<=n;j++)

         {

             sum[i][j]=scan();

             sum[i][j]=(sum[i][j]+sum[i][j-])%p;

         }

     }

     int ans = (sum[][]+sum[][]+sum[][n])%p;

     set<int> s;

     for (int i=;i<=n;i++)

     {

         int tp = (sum[][i]-sum[][i-]+p)%p;

         s.insert( tp );

         int dat = (sum[][i]+sum[][n]-sum[][i-]+p)%p;

         set<int>::iterator it = s.lower_bound(p-dat);

         if (it!=s.end())

         {

             if (it!=s.begin())

             {

                 it--;

                 ans = max((LL)ans,(*it+sum[][i]+sum[][n]-sum[][i-]+p)%p);

             }

         }

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

1624 取余最长路(set)

最新文章

热门文章