题目链接：http://acm.uestc.edu.cn/#/problem/show/1646

题意：求一个有n个元素的数列，满足任意连续p个数的和不小于s，
任意连续q个数的和不大于t。
解法：令sum[i]表示前i项的和(0<=i<=n,sum[0]=0)
那么题目的条件可转化为：
sum[i]-sum[i-p]>=s (p<=i<=n)
sum[i]-sum[i-q]<=t (q<=i<=n)
将第一个不等式取反，得到
sum[i-p]-sum[i]<=-s(p<=i<=n)

于是问题转化为求一系列不等式的解，这是一个典型的差分约束问题。

考虑最短路径的性质，令dis[i]表示从s到i的最短路，则对于图中存在的一条边(u,v),有
dis[v]<=dis[u]+w(u,v),即dis[v]-dis[u]<=w(u,v);
类比不等式，于是可建图，i向i-p引长度为-s的边，i-q向i引长度为t的边。

然后运行bellmanford，如果存在负环，则无解，
否则所得到的最短路的值就是sum[i]的一个解。

时间复杂度：O(VE)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
LL dis[maxn];
int head[maxn], edgecnt, n, p, q, s, t;
int cnt[maxn];
bool inq[maxn];
struct edge{
    int to,w,next;
    edge(){}
    edge(int to, int w, int next) : to(to), w(w), next(next) {}
}E[maxn*10];
void init(){
    edgecnt = 0;
    memset(head, -1, sizeof(head));
}
void add(int u, int v, int w){
    E[edgecnt].to = v, E[edgecnt].w = w, E[edgecnt].next = head[u], head[u] = edgecnt++;
}
bool spfa(){
    queue<int>que;
    for(int i=0; i<=n; i++) dis[i]=inf;
    memset(inq,0,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    dis[0]=0;
    que.push(0);
    inq[0]=1;
    for(int i=1; i<=n; i++){
        que.push(i);
        inq[i]=1;
    }
    while(!que.empty()){
        int u = que.front();
        que.pop();
        inq[u] = 0;
        for(int i=head[u]; ~i; i=E[i].next){
            int v = E[i].to;
            int w = E[i].w;
            if(dis[u] + 1LL*w < dis[v]){
                cnt[v]++;
                dis[v] = dis[u] + 1LL*w;
                if(cnt[v]>n) return false;
                if(!inq[v]){
                    inq[v]=1;
                    que.push(v);
                }
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d %d %d %d %d", &n, &p, &q, &s, &t);
    init();
    for(int i=0; i<=n; i++){
        if(i-p>=0) add(i,i-p,-s);
        if(i-q>=0) add(i-q,i,t);
    }
    if(spfa()){
        printf("Yes\n");
        printf("%lld", dis[1]);
        for(int i=2; i<=n; i++){
            printf(" %lld", dis[i]-dis[i-1]);
        }
        printf("\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}