文章

68

粉丝

691

获赞

24

访问

547.7k

头像
dp
P1147 ICPC大学生程序设计竞赛
发布于2020年5月18日 15:47
阅读数 5.7k

 

#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;

#define inf 0x3f3f3f3f
#define MAX 50
#define ll int 
#define vec vector<ll>
#define P pair<ll,ll>

int n, a[MAX], dp[10005], k;
int main() {
	while (cin >> n >> k) {
		for (int i = 1; i <= n; i++)cin >> a[i];
		memset(dp, 0, sizeof(dp)); dp[0] = 1;
		ll maxj = 0;
		for (int i = 1; i <= n && !dp[k]; i++) {
			for (int j = maxj; j >= 0 && !dp[k]; j--)
				if (dp[j] && j + a[i] <= k) dp[j + a[i]] = 1;
			maxj += a[i];
			maxj = min(maxj, k);
		}
		if (dp[k])cout << "yao bu ni bie gan le ba" << endl;
		else cout << "wo bu yao ni jue de,wo yao wo jue de" << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发