牛客周赛86E题
思路
本题容易想到可构成的多边形需最大边MAX小于其他边的和
令多边形周长为C，则有C-MAX>MAX
所以有C>2*MAX且C尽量小
那么可以判断，MAX越小则C容易越小
于是我们可以从小的边枚举
比该边小或等于的均可作为边的材料
最后将所有C中最小的输出即可
若是没有一个边可以构造C则输出-1
值得注意的是  使用比MAX小的边构造时 令排在MAX前的边和为sum
当sum<=MAX时，不可能构成多边形，可跳过
当枚举的边MAX>先前构造成功的最小周长C的一半时，不论如何构造获得的周长一定小于C
如果可以在sum中选取一些边长和s1>MAX的话(s1+s2=sum)
那么必定其他的边长和s2<sum-MAX
预使C要更小则s2须在小于（sum-MAX）的范围内最大
于是到这里可以转换为背包问题
代码
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const int N=1e5+10;
void solve(){
    int n,s,ans=N;
    cin>>n;
    vector<int>v(n+1);
    for(int i=1;i<=n;i++)
        cin>>v[i];
    sort(v.begin()+1,v.end());
    s=v[1];
    for(int i=3;i<=n;i++){
        s+=v[i-1];
        if(s<=v[i]) continue;
        if(v[i]>=ans/2) break;
        vector<int>dp(s);
        int maxn=v[i];
        for(int j=1;j<i;j++){
            for(int k=s-maxn-1;k>=0;k--)
                if(k>=v[j]) dp[k]=max(dp[k],dp[k-v[j]]+v[j]);
        }
        int c=s-dp[s-maxn-1]+maxn;
        ans=min(c,ans);
    }
    if(ans==N){
        cout<<"-1"<<endl;
        return;
    }
    cout<<ans<<endl;
}
signed main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	int t=1;
	cin>>t;
	while(t--)
	  solve();
	return 0;
}