leetcode-956. 最高的广告牌

https://leetcode-cn.com/contest/weekly-contest-114/problems/tallest-billboard/

给出一个集合，询问能否挑出两个不重叠的子集，使得两个子集内的数字和一样，求数字和最大是多少。

一开始枚举所有集合然后dp一波果断T了。

正解是f(i,j)表示前i个数字，组成的两个集合差为j的时候较大的集合内的数字和，然后枚举一下三种情况dp即可。

一开始少算了一种情况，是把第i加在较小的集合里，仍没超过较大的集合。

 1 class Solution {
 2 public:
 3     #define inf 0x3f3f3f3f
 4     int tallestBillboard(vector<int>& rods) {
 5         int f[21][5005];
 6         memset(f,-inf,sizeof(f));
 7         f[0][0]=0;
 8         for(int i=0;i<rods.size();++i){
 9             for(int j=0;j<=5000;++j){
10                 f[i+1][j]=max(f[i+1][j],f[i][j]);
11                 if(j>=rods[i]&&f[i][j-rods[i]]!=-inf)f[i+1][j]=max(f[i+1][j],rods[i]+f[i][j-rods[i]]);
12                 if(rods[i]>=j&&f[i][rods[i]-j]!=-inf)f[i+1][j]=max(f[i+1][j],j+f[i][rods[i]-j]);
13                 if(j+rods[i]<=5000&&f[i][j+rods[i]])f[i+1][j]=max(f[i+1][j],f[i][j+rods[i]]);
14             }
15         }
16         return max(0,f[rods.size()][0]);
17     }
18 };