当前位置:网站首页>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;
}
边栏推荐
- 教你在HbuilderX上使用模拟器运行uni-app,良心教学!!!
- Choose to pay tribute to the spirit behind continuous struggle -- Dialogue will values [Issue 4]
- Codeforces Round #804 (Div. 2)【比赛记录】
- Initialiser votre vecteur & initialisateur avec une liste Introduction à la Liste
- 多普勒效應(多普勒頻移)
- Hudi of data Lake (2): Hudi compilation
- Mathematical model Lotka Volterra
- Doppler effect (Doppler shift)
- Redis high availability - master-slave replication, sentinel mode, cluster
- PHP determines whether an array contains the value of another array
猜你喜欢
云呐|公司固定资产管理系统有哪些?
提升工作效率工具:SQL批量生成工具思想
Mysql - CRUD
Hudi of data Lake (2): Hudi compilation
What are the functions of Yunna fixed assets management system?
软件测试工程师必会的银行存款业务,你了解多少?
About the slmgr command
Mathematical model Lotka Volterra
Start from the bottom structure and learn the introduction of fpga---fifo IP core and its key parameters
Key structure of ffmpeg - avframe
随机推荐
Global and Chinese market of digital serial inverter 2022-2028: Research Report on technology, participants, trends, market size and share
Permission problem: source bash_ profile permission denied
QT QPushButton details
NSSA area where OSPF is configured for Huawei equipment
[noi simulation] Anaid's tree (Mobius inversion, exponential generating function, Ehrlich sieve, virtual tree)
FFT 学习笔记(自认为详细)
上门预约服务类的App功能详解
Yunna | what are the main operating processes of the fixed assets management system
如何解决ecology9.0执行导入流程流程产生的问题
Shardingsphere source code analysis
Make a short video clip number of we media film and television. Where can I download the material?
Browser local storage
Determinant learning notes (I)
Global and Chinese markets of universal milling machines 2022-2028: Research Report on technology, participants, trends, market size and share
Doppler effect (Doppler shift)
Global and Chinese market of valve institutions 2022-2028: Research Report on technology, participants, trends, market size and share
云呐|固定资产管理系统主要操作流程有哪些
LeetCode 6005. The minimum operand to make an array an alternating array
Miaochai Weekly - 8
Huawei equipment is configured with OSPF and BFD linkage