https://ac.nowcoder.com/acm/contest/560/K
难道我连DP怎么写都忘了???
看代码吧
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n) for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
#define PII pair<int,int>
#define PB push_back
#define x first
#define y second
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint>
inline void IN(INint &x)
{
x = 0; int f = 1; char c; cin.get(c);
while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(105);
const int maxv = 55;
int dp1[maxn][maxv*maxn];
int dp2[maxn][maxv*maxn];
int a[maxn];
int& dp(int i, int dif)
{
if (dif >= 0)return dp1[i][dif];
else return dp2[i][-dif];
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
int T(1), times(0);
#ifdef CPP_IO// CPP_IO
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
#else
//IN(T);
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////
while (++times, T--)
{
int n; cin >> n;
int sum(0);
RE2(i, n)cin >> a[i], sum += a[i];
RE2(i, n)for (int j = -maxn*maxv+1; j <maxn*maxv; ++j)dp(i, j) = -inf;
dp(0, 0) = 0;
dp(1, a[1]) = 1;
dp(1, -a[1]) = 1;
dp(1, 0) = 0;
RE2(i, n - 1)
{
for (int j = -maxn*maxv + 1; j < maxn*maxv; ++j)if (dp(i, j) != -inf)
{
dp(i + 1, j) = max(dp(i + 1, j), dp(i, j));
dp(i + 1, j + a[i + 1]) = max(dp(i + 1, j + a[i + 1]), dp(i, j) + 1);
dp(i + 1, j - a[i + 1]) = max(dp(i + 1, j - a[i + 1]), dp(i, j) + 1);
}
}
cout << n - dp(n, 0) << endl;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
return 0;
}