状压dp,40分求调试
查看原帖
状压dp,40分求调试
918894
XyGetItRightAker楼主2023/10/29 12:03
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
int read();
struct node {
	int t, d, l;
}num[11];
int f[(1 << 11)];
int main() {
	int n;
	int t;
	t = read();
	for (int i = 1; i <= t; i++) {
		n = read();
		memset(f, 0x7f, sizeof(f));
		for (int j = 1; j <= n; j++) {
			num[j].t = read();
			num[j].d = read();
			num[j].l = read();
			f[1 << j - 1] = num[j].t + num[j].l;
		}
		for (int j = 1; j < 1 << n; j++) {

			for (int k = 1; k <= n; k++) {
				if (1 << k - 1 & j) {
					if (f[j - (1 << k - 1)] > num[k].t + num[k].d)continue;
					f[j] = min(f[j], f[j - (1 << k - 1)]+num[k].l);
				}

			}

		}
		
		if (f[(1 << n) - 1] == 0x7f7f7f7f) {
			cout << "NO" << endl;
		}
		else {
			cout << "YES" << endl;
		}




	}
	return 0;
}

int read() {
	char ch = getchar();
	int res = 0;
	while (ch > '9' || ch < '0') {
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		res = res * 10 + ch - '0';
		ch = getchar();
	}
	return res;
}

2023/10/29 12:03
加载中...