题目描述：

长度为n的数组， x[i]表示其中第i个元素 1 <= i <= n

给你m个条件，

每个条件有 a b c d四个值

c表示大于或者小于。

这个条件表述为：x[a] + x[a + 1] + x[a + 2] + ... + x[a + b] < (或者>) d

问，这个有没有可能存在一个同时满足这m个条件的数组

解题报告：

设f[i] 表示 x[1] + ... + x[i - 1],

则a b c d条件可以表述为

f[a + b] - f[a - 1] < （或者>) d

转化成了差分约束，用bellman即可。

代码如下：

#include<iostream>
using namespace std;
#define size 101
#define Max 2000000000
int d[size], ecnt, n, m;
struct edge{int from, to, v;}e[size];
bool bellman()
{
    for(int i = 1; i <= n; i++) d[i] = Max;
    d[0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < ecnt; j++)
            if (d[e[j].from] + e[j].v < d[e[j].to])
                d[e[j].to] = d[e[j].from] + e[j].v;
    for(int j = 0; j < ecnt; j++)
        if (d[e[j].from] + e[j].v < d[e[j].to]) return false;
    return true;
}
int si, ni, ki;
char oi[4];
int main()
{
    while(scanf("%d", &n) && n)
    {
        scanf("%d", &m);ecnt = 0;
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%s%d", &si, &ni, oi, &ki);
            int l = si - 1, r = si + ni;
            if (strcmp(oi, "gt") == 0)
            {
                e[ecnt].from = r;
                e[ecnt].to = l;
                e[ecnt].v = ki * -1 - 1;
            }
            else
            {
                e[ecnt].from = l;
                e[ecnt].to = r;
                e[ecnt].v = ki - 1;
            }
            ecnt++;
        }
        if (!bellman()) printf("successful conspiracy\n");
        else printf("lamentable kingdom\n");
    }
    return 0;
}