UVa12455

題敘

http://domen111.github.io/UVa-Easy-Viewer/?12455

想法

對於每個長度的棍子都可以用其他棍子組合而成
定義 $DP[i]$ 表示可以組成長度i的棍子
則有 $DP[i] = DP[i-k] ,k \leq i$
對於每個棍子都看看能不能透過這個棍子與其他棍子的組合組成新的長度

Code

//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int t,n,p,arr[1005],dp[1005];
int main(){
	IOS
	cin>>t;
	while(t--){
		cin>>n>>p;
		for(int i=0 ; i<1005 ; i++)dp[i]=0;
		for(int i=0 ; i<p ; i++){
			cin>>arr[i];
		}
		dp[0]=1;
		//dp[i]=dp[i-k], k<=i
		for(int i=0 ; i<p ; i++){
			for(int j=n ; j>=arr[i] ; j--){
				if(dp[j-arr[i]])
					dp[j]=1;
			}
		}
		if(dp[n])
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}

複雜度

共有n種狀態，每種狀態轉移複雜度為 $O(1)$
總複雜度為 $O(n)$