每日一题：走路

.走路 - 题目 - Daimayuan Online Judge

f[i][j]表示第i步能否走到第j阶

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N=110,M= 100010;
bool f[N][M];
int a[N], b[N];
signed main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    f[0][0] = true;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= m; j++) {
            if(f[i-1][j]&&j+a[i]<=m) f[i][j+a[i]]=true;
                if(f[i-1][j]&&j+b[i]<=m) f[i][j+b[i]]=true;
        }
    }
    for (int j = 0; j <= m; j++) {
        if(f[n][j]) cout<<1;
        else cout<<0;
    }
}