[TIOJ] 1993. 冰塊塔

題目連結:http://tioj.infor.org/problems/1993

---

DP題可以滾動，狀態大概就是$dp[i][j]$代表可否用前j個數湊出i，滾起來後就剩一維了，而且還會發現其實我每次在做的事情其實就是把他在往後移某個格數，所以可以用bitset的位移來達到優化的效果(自己$O(N)$位移會是爛的QQ)
p.s. 其實bitset位移好像也是$O(N)$，但常數超小(我這裡真的找不太到資料，但他跑起來超快)

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

bitset<N> isok;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t; cin>>t;
	while(t--){
		isok.reset();
		isok[0]=1;
		int n, m; cin>>n>>m;
		for(int i=0;i<n;i++){
			int a, b, c; cin>>a>>b>>c;
			isok = (isok<<a)|(isok<<b)|(isok<<c);
		}
		int ans = 0;
		for(int i=0;i<=m;i++) if(isok[i])
			ans = i;
		if(ans==0) cout<<"no solution\n";
		else cout<<ans<<'\n';
	}
	return 0;
}