2013 장사 인터넷 경기 J 문제 캔디 스 (차분 구속 또는 수학 법칙) \ # by zh

이 문 제 는 정말 정신 이 없 었 습 니 다. 방금 이 문 제 를 받 았 습 니 다. 잠시 생각 했 더 니 차이 점 으로 제약 할 수 있 을 것 같 았 습 니 다. 다 쓴 후에 약간 조 정 했 습 니 다. WA 를 제출 했 습 니 다. 조금 고 쳤 는데 도 WA 였 습 니 다. 알고리즘 이 틀린 줄 알 았 습 니 다.그리고 규칙 적 인 것 을 발 견 했 고 수학 방법 으로 바 꾸 었 습 니 다. 약간 좌절 되 었 고 데 이 터 를 내 서 bug 를 많이 조 정 했 지만 WA 가 죽 을 때 까지 만 들 지 못 했 습 니 다.오늘 또 생각해 보 니 팀 원 들 은 각 점 에서 값 을 얻 는 범위 가 0 에서 10000 이 아니 라 마이너스 라 는 것 을 발견 하고 어 쩔 수 없 이 제목 의 진심 을 토로 한 다음 에 이전의 두 코드 를 모두 10000 의 제약 을 없 앤 후에 모두 지 났 다.문 제 를 읽 는 것 은 경상 이다.
계차 제약: 전 i 개인 이 돌 개 수 를 가 진 최대 가능 치 와 최소 가능 치 를 각각 유지 합 니 다. i 개인 이 가능 한 최대 수 치 는 dismax [i] - dismin [i - 1] 입 니 다.
수학 규칙: 3, 6, 9,..........................................................................

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 100005
int dismax[MAXN],dismin[MAXN];
int vis[MAXN];
const int INF=0x3f3f3f3f;
struct Node
{
    int v,w;
    Node(int a,int b){v=a,w=b;}
};
int n;
vector<Node> gmin[MAXN],gmax[MAXN];
void spfamax()
{
    for(int i=0;i<=n;i++)
        dismax[i]=INF;
    memset(vis,0,sizeof(vis));
    dismax[0]=0;
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        int len=gmax[u].size();
        for(int i=0;i<len;i++)
        {
            int v=gmax[u][i].v,w=gmax[u][i].w;
            if(dismax[v]>dismax[u]+w)
            {
                dismax[v]=dismax[u]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
}
void spfamin()
{
    for(int i=0;i<=n;i++)
        dismin[i]=-INF;
    memset(vis,0,sizeof(vis));
    dismin[0]=0;
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        int len=gmin[u].size();
        for(int i=0;i<len;i++)
        {
            int v=gmin[u][i].v,w=gmin[u][i].w;
            if(dismin[v]<dismin[u]+w)
            {
                dismin[v]=dismin[u]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    //freopen("test.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=n;i++)
            gmin[i].clear(),gmax[i].clear();
        for(int i=1;i<=n;i++)
        {
            gmax[i].push_back(Node(i-1,0));
            gmin[i-1].push_back(Node(i,0));
        }
        for(int i=1;i<=n;i++)
        {
            int temp;
            scanf("%d",&temp);
            if(temp!=-1)
            {
                gmax[i-1].push_back(Node(i,temp));
                gmax[i].push_back(Node(i-1,-temp));
                gmin[i-1].push_back(Node(i,temp));
                gmin[i].push_back(Node(i-1,-temp));
            }
        }
        for(int i=1;i<=n;i++)
        {
            int w;
            scanf("%d",&w);
            int u=max(0,i-2),v=min(n,i+1);
            gmax[u].push_back(Node(v,w));
            gmax[v].push_back(Node(u,-w));
            gmin[u].push_back(Node(v,w));
            gmin[v].push_back(Node(u,-w));
        }
        spfamax();
        spfamin();
        int q;
        scanf("%d",&q);
        for(int i=0;i<q;i++)
        {
            int temp;
            scanf("%d",&temp);
            temp++;
            printf("%d
",dismax[temp]-dismin[temp-1]);
        }
    }
}