BZOJ4978: [Lydsy1708月赛]泛化物品（乱搞）

4978: [Lydsy1708月赛]泛化物品

Time Limit: 5 Sec Memory Limit: 256 MB
Submit: 220 Solved: 70
[Submit][Status][Discuss]

Description

泛化物品是背包问题里的一个概念，泛化物品并没有固定的体积和费用，而是它的费用随着分配给它的体积而变化

。在背包容量为V-1的背包问题中，泛化物品是一个定义域为[0,V)中的整数的函数h，当分配给它的体积为v时，花

费的费用就是h(v)。这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0..V-1]，给它体积v，费

用为h[v]。这就是所谓的泛化物品。定义泛化物品的和：g,h都是泛化物品，若泛化物品f满足f(v)=min{g(k)+h(v-

k)}，其中0<=k<=v且0<=k,v-k<n，则称f是g与h的和，即f=g+h。现给定两个定义域均为[0,n)的泛化物品a,b，试求

出c=a+b。

Input

第一行包含一个正整数n(1<=n<=100000)，表示定义域中的n。

第二行包含n个整数a_0,a_1,...,a_{n-1}(0<=a_i<n)，表示泛化物品a。

第三行包含n个整数b_0,b_1,...,b_{n-1}(0<=b_i<n)，表示泛化物品b。

输入数据保证a和b都是0到n-1的随机排列。

Output

对于每组数据输出一行2n-1个整数，依次表示c_0,c_1,...,c_{2n-2}。

Sample Input

5
3 4 2 0 1
2 3 0 4 1

Sample Output

5 6 3 2 2 0 1 1 2

HINT

Source

思路：没有什么特别的方法，但是由于数据是随机的，我们可以排序，先得出大部分结果，然后剩余部分靠暴力。

排序是指a，b分别排序，用最小的部分更新答案。这里只用前2000个就ok的。

（不知道为什么我两个上面的两个for语句为什么就错了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
const int inf=1e9;
int a[maxn],pos1[maxn],b[maxn],pos2[maxn],ans[maxn];
int main()
{
    int N; scanf("%d",&N);
    rep(i,0,2*(N-1)) ans[i]=inf;
    rep(i,0,N-1) scanf("%d",&a[i]),pos1[a[i]]=i;
    rep(i,0,N-1) scanf("%d",&b[i]),pos2[b[i]]=i;
    rep(i,0,2*(N-1)) ans[i]=inf;
    /*rep(i,0,min(N-1,2000)) 但是不知道这个为什么是错的
     rep(j,0,min(N-1,2000)){
        int p=pos1[i]+pos2[j];
        ans[p]=min(ans[p],i+j);
    }*/
    rep(i,0,min(2000,2*(N-1)))
     rep(j,max(0,i-(N-1)),min(i,N-1)){
        int p=pos1[j]+pos2[i-j];
        ans[p]=min(ans[p],i);
    }
    rep(i,0,2*(N-1)) {
        if(ans[i]>=inf){
            rep(j,max(0,i-(N-1)),min(i,N-1))
              ans[i]=min(ans[i],a[j]+b[i-j]);
        }
    }
    rep(i,0,2*(N-1)) printf("%d ",ans[i]);
    return 0;
}