题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000;
int s[N];
int a[N][N];
int l,r,ans = 1e9;
int res;
void work(int cnt,int p)
{
if(cnt > s[p])
{
ans = min(ans,max(l,r));
return ;
}
l += a[p][cnt];
work(cnt+1,p);
l -= a[p][cnt];
r += a[p][cnt];
work(cnt+1,p);
r -= a[p][cnt];
}
int main()
{
for(int i = 1;i<=4;i++) cin >> s[i];
for(int i = 1;i<=4;i++)
{
for(int j = 1;j<=s[i];j++)
{
cin >> a[i][j];
}
l = 0;
r = 0;
ans = 1e9;
work(1,i);
res += ans;
}
cout << res << endl;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N];
int s[N];
int f[N];
int ans;
int sum;
int work(int n)
{
int m = sum / 2;
for(int i = 1;i<=n;i++)
{
for(int j = m;j>=a[i];j--)
{
f[j] = max(f[j],f[j-a[i]] + a[i]);
}
}
return max(f[m],sum - f[m]);
}
int main()
{
for(int i = 1;i<=4;i++)
{
cin >> s[i];
}
for(int i = 1;i<=4;i++)
{
memset(f,0,sizeof f);
sum = 0;
for(int j = 1;j<=s[i];j++)
{
cin >> a[j];
sum += a[j];
}
ans += work(s[i]);
}
cout << ans << endl;
return 0;
}