[DP]JZOJ 1758 过河

Description

　　在BYTELAND的许多市民极喜爱那些逻辑思考与物理技巧同样重要的运动。有一种运动是过HEX河——BYTELAND中最宽的河流。有n根柱子，从1到n进行编号（从左至右），跨过这条河流。市民过河不得不如此：从河的左岸走至一根柱上，可能再走到下一根柱上，如此下去，最后到达河右岸。左岸有一根柱子设置在柱子1的左侧，右岸有一根柱子设置在柱子n的右侧。
　　在0时刻，有一市民站在左岸，他想尽快到达河的右岸。任意时刻，每一根柱子或者浮上来或者沉下去，市民或者站在某根柱上或者站在河岸。一个市民只有当柱子浮上时方能站在柱上，这样的柱子才是可靠的，。
　　每根柱在0时刻沉下去，然后有a个时间单元浮上来，b个时间单元沉下去，再有a个时间单元浮上来，b个时间单元沉下去，等等。常数a和b对每根柱分别进行定义。例如，对a=2,b=3的某根柱，他在0时刻沉下去，在1，2时刻浮上来；3，4，5时刻沉下去，等等。
　　在t+1时刻，市民可以选择距离t时刻所在位置5根柱子之内的可靠的柱子上﹑岸上，或者站在当前的柱子上（如果可靠）或岸上。例如，从柱子5，你能到达下列的任意一根柱子1，2，3，4，5，6，7，8，9，10或者左岸。
写一个程序：从文件RIV.IN中读取数据的组数（每组包括对该题目的一套数据）；对每一组
　　﹡读取柱子的数目和对他们的描述；
　　﹡计算出市民首先到达河右岸的时刻，如果它能够到达；
　　﹡将结果写至文件RIV.OUT上。

 

Input

　　文件RIV.IN的第一行包含数据的组数x(1≦x≦5),接下来的许多行组成了这x组数。第一组从输入文件的第二行开始，，接下来的每个组直接接在上一组之后。
　　每组的第一行包括一个整数N,5<N≦1000,表示柱子的数量。该组中接下来的n行，每行包括两个整数a,b,被一空格隔开，1≦a,b≦5。第i+1行（该组中）的整数1≦i≦n,描述柱i的行为。

Output

　　对第k组，1≦k≦x, 在文件RIV.OUT的第k行写出市民最先能到达河右岸的时刻，或者写上单词No,如果不可能过河。

 

Sample Input

2                                          
10                                         
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
10
1 1
1 1
1 1
1 1
2 1
1 1
1 1
1 1
1 1
1 1

Sample Output

No
4

 

Data Constraint

分析

通过分析会发现答案不超过5000（待验证）

所以设f[i][j]表示第i个时刻能否在第j个石柱上

暴力DP即可

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int N=1e3+10; 
int x;
int n,a[N],b[N];
bool f[5010][N],ok;

int main() {
    for (scanf("%d",&x);x;x--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
        memset(f,0,sizeof f);f[0][0]=1;ok=0;
        for (int i=1;i<=5000;i++) {
            for (int j=0;j<=n+1;j++)
                if (j==0||j==n+1||i%(a[j]+b[j])>=1&&i%(a[j]+b[j])<=a[j]) {
                    for (int k=-5;k<=5;k++)
                        if (j+k>=0&&j+k<=n+1&&f[i-1][j+k]) {
                            f[i][j]=1;
                            if (j==n+1) {
                                printf("%d
",i);
                                ok=1;
                            }
                            break;
                        }
                    if (ok) break;
                }
            if (ok) break;
        }
        if (!ok) printf("No
");
    }
}