Daimayuan 走路

题目地址：http://oj.daimayuan.top/problem/460

输入样例：

3 10
1 2
2 6
3 3
           

输出样例：

00000011001
           

思路

就是一道简单 d p dp dp的题，我们用一个二维数组标记我们每一步可以走到的所有位置，最后输出 d p [ n − 1 ] [ m ] dp[n-1][m] dp[n−1][m]即可（从第0行开始的条件下）。

代码

#include<bits/stdc++.h>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define inf 1e9
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+9;
int t, n, m, k;
pii p[110];
int dp[100][N];
void solve(){
	std::cin>>n>>m;
	for(int i = 0;i < n;i++){
		int a, b;
		std::cin>>a>>b;
		p[i] = {a,b};
	}
	for(int i = 0;i < n;i++){
		for(int j = 1;j < m;j++){
			if(i==0){
				dp[i][p[i].first] = 1;
				dp[i][p[i].second] = 1;
				continue;
			}
			// cout<<dp[i-1][j]<<" ";
			if(dp[i-1][j]==1){
				dp[i][j+p[i].first] = 1;
				dp[i][j+p[i].second] = 1;
				dp[i-1][j] = 0;
			}
		}
		// cout<<"\n";
	}
	for(int i = 0;i <= m;i++)std::cout<<dp[n-1][i];
}
int main(){
	// std::cin>>t;
	// while(t--)
		solve();
	return 0;
}