列表

详情

NC245409. Lego

描述

Wings loves playing Lego! Today, Wings is playing a strange set of Lego blocks. There are n symmetrical elongated blocks in this set. For some blocks, the number of bottom slots is not equal to the number of top slots. The picture below shows examples of such blocks.

Wings sorts these blocks so that the number of bottom slots is in non-decreasing order and numbers them from 1 to n. He also notices that the number of top slots is in non-increasing order.
Wings wants to pick m blocks for his building. He fifirst picks the block p1, places it on the table. In the following time, he picks the block pi (pi > pi−1), and puts it on block pi−1. Wings can assemble two blocks horizontally or vertically. The picture below shows all the different ways of assembling two certain blocks.

Note that even the fifirst can be rotated to get the third, but the whole stack may not be symmetric, so we consider it to be assembled differently. The same goes for the fourth and seventh, and the fififth and sixth.
However, when Wings picks one block, and there are k different ways of assembling, it will take him k seconds to decide how to assemble. Wings wants to know the earliest time he can complete his building.



输入描述

The fifirst line contains a single integer T (1 ≤ T ≤ 10), denoting the number of test cases.
In each test case, the fifirst line contains two space-separated integers n and m (2 ≤ m ≤ n ≤ 1000). n denotes the number of Lego bricks. And m denotes the number of bricks Wings wants to pick.
The next line contains n space-separated integers ai (2 ≤ ai ≤ 105 ), denoting the number of slots at the bottom of each brick.
The next line contains n space-separated integers bi (2 ≤ bi ≤ 105 ), denoting the number of slots at the top of each brick.
It is guaranteed that ai is non-decreasing and bi is non-increasing.

输出描述

For each test case, output a single integer in a line, representing the earliest time Wings could complete the building.

示例1

输入: 

2
2 2
2 2
2 2
5 3
2 2 4 5 5
6 4 4 3 2

输出: 

7
42

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 62ms, 内存消耗: 7388K, 提交时间: 2022-11-30 01:54:46 

#include <bits/stdc++.h>
#define pb push_back
#define ALL(tar) tar.begin(), tar.end()
#define forn(name, b, n) for (int name = (b); name < (n); name++)
#define competition cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<pair<int, ii> > EdgeList;
const ll INF = 0x3f3f3f3f;
const ll MOD = 998244353;
const ll MS = 1010;
ll dp[MS][MS];
ll a[MS],b[MS];
#define Y(o,p,i) (dp[p][i-1]+b[p]-dp[o][i-1]-b[o])
#define X(o,p) (-b[p]+b[o])
int q[MS],l,r;
int main()
{
	//freopen("in.txt","r",stdin);
	competition;
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		forn(i,1,n+1)cin>>a[i];
		forn(i,1,n+1)cin>>b[i];
		//forn(i,1,n+1)dp[i][1]=0;
		l=1,r=0;
		forn(i,2,m+1){
			l=1,r=0;
//			forn(j,1,i+1){
//				while(l<r&&Y(q[r],j,i)*X(q[r-1],q[r])>=Y(q[r-1],q[r],i)*X(q[r],j))--r;
//				q[++r]=j;
//			}
			q[l=r=1]=i-1;
			forn(j,i,n+1){
				while(l<r&&a[j]*X(q[l],q[l+1])>=Y(q[l],q[l+1],i))++l;
				dp[j][i]=dp[q[l]][i-1]+b[q[l]]+a[j]-1+a[j]*b[q[l]];
				while(l<r&&Y(q[r],j,i)*X(q[r-1],q[r])<=Y(q[r-1],q[r],i)*X(q[r],j))--r;
				q[++r]=j;
			}
		}
		ll ans=2e18;
		forn(i,m,n+1)
		ans=min(ans,dp[i][m]);
		printf("%lld\n",ans);
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 73ms, 内存消耗: 7360K, 提交时间: 2022-10-24 15:08:36 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

using i64 = long long;

const int N = 1010;

int a[N], b[N];
int n, m;
i64 f[N][N];
int q[N];

i64 y(int u, int i) {
    return f[u][i] + b[i];
}

i64 x(int i) {
    return -b[i];
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    memset(f, 0x3f, sizeof f[1]);
    f[1][1] = 0;
    for (int u = 2; u <= m; u++) {
        int tt = -1, hh = 0;
        q[++tt] = u - 1;
        for (int i = u; i <= n; i++) {
            i64 k = a[i];
            while (hh < tt && y(u - 1, q[hh + 1]) - y(u - 1, q[hh]) <= k * (x(q[hh + 1]) - x(q[hh]))) hh++;
            int j = q[hh];
            f[u][i] = y(u - 1, j) - k * x(j) + a[i] - 1;
            while (hh < tt && (y(u - 1, q[tt]) - y(u - 1, q[tt - 1])) * (x(i) - x(q[tt]))
                >= (y(u - 1, i) - y(u - 1, q[tt])) * (x(q[tt]) - x(q[tt - 1]))) tt--;
            q[++tt] = i;
        }
    }
    i64 res = 1e18;
    for (int i = m; i <= n; i++) res = min(res, f[m][i]);
    cout << res << '\n';
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

上一题

© 2024 nowcoder.com