题解 | #数组分组#
数组分组
https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86?tpId=37&tqId=21316&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D4%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=4&judgeStatus=undefined&tags=&title=
#include <iostream>
#include <vector>
using namespace std;
int dp[64][2048], arr[64]; // t1 - t2 + 1000: [0, 2000]
int main()
{
int n, p=0, t, sum1 = 0, sum2 = 0;
cin>>n;
for(int i = 0; i<n;i++){
cin>>t;
if(t % 5 == 0)sum1 += t;
else if(t%3 == 0) sum2 += t;
else arr[++p]=t;
}
dp[0][sum1-sum2+1000]=1;
for(int i = 1;i<=p;i++){
for(int j = arr[i]; j+arr[i]<=2000; j++){
// t1-(t2+arr[i])+1K = j -> t1-t2+1k = j+arr[i]
dp[i][j] |= dp[i-1][j+arr[i]]; // put into t2
// (t1+arr[i])-t2+1K = j -> t1-t2+1k = j-arr[i]
dp[i][j] |= dp[i-1][j-arr[i]]; // put into t1
}
}
if(dp[p][1000])cout<<"true"<<endl;
else cout<<"false"<<endl;
return 0;
}
