当前位置:网站首页>Codeforces gr19 D (think more about why the first-hand value range is 100, JLS yyds)
Codeforces gr19 D (think more about why the first-hand value range is 100, JLS yyds)
2022-07-06 00:14:00 【Find a derivative first】
subject
The question : Given array a、b, You can exchange any number i Location a[i] and b[i], Make the formula in the following figure minimum .(n<=100,a[i]、b[i]<=100)
Ideas : We must simplify the formula first , Otherwise, I don't know what to do . After simplification, I found that I didn't care about the square term , Just focus on the minimum sum of squares of the sum of two arrays . Can pass dp Find out all the values that can be obtained by one of the arrays , You can find the minimum value .
Method 1: f[i][j]: Before use only i Number , Make and for j.true It means you can come up with . Because the maximum is 100, most 1e6. ( The first dimension can be optimized as 0、1)
Method 2: You might as well change the small numbers to a in , Big numbers are put in b in . adopt dp Find out through exchange ,a Array new sum , Record minimum . It can be used bitset maintain a Arrays are swapped to get new sums .
Time complexity : O(nmaxmax = 1e6), It can be used bitset Optimize ,emmm Feeling is 8 times ? But the explanation is 64 times , Don't know much about .
Code :
bitset
#include<bits/stdc++.h>
using namespace std;
const int MAXSUM = 100*100+10;
int n,m,k,T;
int fun(int x)
{
return x * x ;
}
void solve()
{
scanf("%d",&n);
vector<int> a(n+1),b(n+1);
long long ans = 0; int l = 0,r = 0; // and
for(int i=1;i<=n;++i) scanf("%d",&a[i]),ans += fun(a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]),ans += fun(b[i]);
for(int i=1;i<=n;++i)
{
if(a[i] > b[i]) swap(a[i],b[i]);
l += a[i];
r += b[i];
}
ans *= (n-2);
int res = 1e9;
bitset<MAXSUM> dp;
dp[0] = 1;
for(int i=1;i<=n;++i)
{
dp |= (dp<<(b[i]-a[i]));
}
for(int i=0;i<=r-l;++i)
{
if(dp[i])
res = min(res,fun(l+i)+fun(r-i));
}
ans += res;
printf("%lld\n",ans);
}
signed main(void)
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
Ordinary dp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<complex>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<list>
#include<set>
#include<queue>
#include<stack>
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i<=b;++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define p_ priority_queue
// round() rounding ceil() Rounding up floor() Rounding down
// lower_bound(a.begin(),a.end(),tmp,greater<ll>()) First less than or equal to
// #define int long long //QAQ
using namespace std;
typedef complex<double> CP;
typedef pair<int,int> PII;
typedef long long ll;
// typedef __int128 it;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int N = 102;
const int M = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-6;
inline int lowbit(int x){
return x&(-x);}
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){
if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){
x = x*10+ch-48;ch=getchar();}x*=f;
}
int n,m,k,T;
bool f[N][N*N];
int a[N];
int b[N];
int fun(int x)
{
return x * x ;
}
void solve()
{
read(n);
int ans = 0;
int res = 1e9;
int sum = 0;
for(int i=1;i<=n;++i)
{
read(a[i]); ans += fun(a[i]); sum += a[i];
}
for(int i=1;i<=n;++i)
{
read(b[i]); ans += fun(b[i]); sum += b[i];
}
ans *= (n-2);
f[0][0] = true;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=sum;++j)
{
if(f[i-1][j])
{
f[i][j+a[i]] = true;
f[i][j+b[i]] = true;
}
}
}
for(int j=0;j<=sum;++j)
{
if(f[n][j])
{
res = min(res,fun(j)+fun(sum-j));
}
}
ans += res;
write(ans); puts("");
}
signed main(void)
{
// T = 1;
// OldTomato; cin>>T;
read(T);
while(T--)
{
solve();
}
return 0;
}
边栏推荐
- What are the functions of Yunna fixed assets management system?
- Doppler effect (Doppler shift)
- What if the C disk is not enough? Let's see how I can clean up 25g of temp disk space after I haven't redone the system for 4 years?
- MySql——CRUD
- MySQL之函数
- Wechat applet -- wxml template syntax (with notes)
- 【DesignMode】适配器模式(adapter pattern)
- 单商户V4.4,初心未变,实力依旧!
- 【GYM 102832H】【模板】Combination Lock(二分图博弈)
- 传输层协议------UDP协议
猜你喜欢
微信小程序---WXML 模板语法(附带笔记文档)
Yunna | what are the main operating processes of the fixed assets management system
Qt QPushButton详解
妙才周刊 - 8
Single merchant v4.4 has the same original intention and strength!
Determinant learning notes (I)
从底层结构开始学习FPGA----FIFO IP核及其关键参数介绍
多普勒效應(多普勒頻移)
N1 # if you work on a metauniverse product [metauniverse · interdisciplinary] Season 2 S2
FFMPEG关键结构体——AVFormatContext
随机推荐
Recognize the small experiment of extracting and displaying Mel spectrum (observe the difference between different y_axis and x_axis)
Atcoder beginer contest 254 [VP record]
Permission problem: source bash_ profile permission denied
Global and Chinese market of valve institutions 2022-2028: Research Report on technology, participants, trends, market size and share
剖面测量之提取剖面数据
第16章 OAuth2AuthorizationRequestRedirectWebFilter源码解析
SQLServer连接数据库读取中文乱码问题解决
转:未来,这样的组织才能扛住风险
【DesignMode】装饰者模式(Decorator pattern)
LeetCode 1189. Maximum number of "balloons"
18. (ArcGIS API for JS) ArcGIS API for JS point collection (sketchviewmodel)
亲测可用fiddler手机抓包配置代理后没有网络
Global and Chinese market of digital serial inverter 2022-2028: Research Report on technology, participants, trends, market size and share
"14th five year plan": emphasis on the promotion of electronic contracts, electronic signatures and other applications
微信小程序---WXML 模板语法(附带笔记文档)
Priority queue (heap)
What is information security? What is included? What is the difference with network security?
LeetCode 1598. Folder operation log collector
【luogu P3295】萌萌哒(并查集)(倍增)
关于slmgr命令的那些事