51Nod-1624-取余最短路

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]

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100100;
long long mz[5][MAXN],pre[5][MAXN];
set<long long> st;
set<long long> ::iterator it;
int main()
{
long long n,mod,i,j,ans,x1,x2;
while(~scanf("%lld%lld",&n,&mod))
{
for(i=1;i<=3;i++)
for(j=1;j<=n;j++)
scanf("%lld",&mz[i][j]);
pre[1][0]=pre[2][0]=pre[3][0]=0;
for(i=1;i<=3;i++)
for(j=1;j<=n;j++)
pre[i][j]=(mz[i][j]+pre[i][j-1])%mod;
st.clear();
ans=0;
for(i=1;i<=n;i++)
{
x1=(pre[1][i]-pre[2][i-1]+mod)%mod;
st.insert(x1);
x2=(pre[3][n]-pre[3][i-1]+pre[2][i]+mod)%mod;
it=st.lower_bound(mod-x2);
ans=max(ans,(x2+*(--it))%mod);
}
printf("%lldn",ans);
}
}

最后

以上就是贤惠彩虹为你收集整理的51Nod-1624-取余最短路的全部内容，希望文章能够帮你解决51Nod-1624-取余最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。