这周主要加强了对知识点的掌握。
P10161 [DTCPC 2024] 小方的疑惑 10
从题目可以得知a个连续括号贡献为a(a+1)/2,代价为2a。要求总贡献恰为k,且代价不高于n。
一开始我想到了模拟,先取一个贡献低于k最大的a,剩下的再直接在外面套括号,结果wa。
又想到可以分出多个a来组成k,就用递归,每次取剩余贡献里最大的a,还是wa。
最后发现问题可以类比到dp问题,对每个k进行dp,记录每个最小代价的方案,然后根据所给n,k输出即可
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
int a[1005],b[100005];
vector<int> q[100005];
void f(int x,vector<int> t){
if(x==t.size())return;
for(int i=0;i<t[x];i++){
if(i)printf("()");
else{
printf("(");
f(x+1,t);
printf(")");
}
}
}
int32_t main() {
int T=1;
cin >> T;
for(int i=0;i<450;i++){
a[i]=i*(i+1)/2;
}
for (int u = 1; u <=100000; u++){
int mn=INT64_MAX,mi=1;
for (int i = 1; a[i]<=u; i++){
if(b[u-a[i]]<mn){
mi=i;
mn=b[u-a[i]];
}
}
b[u]=mn+mi;
for(int i=0;i<q[u-a[mi]].size();i++){
q[u].emplace_back(q[u-a[mi]][i]);
}
q[u].emplace_back(mi);
}
while (T--) {
int n,k;
cin>>n>>k;
if(b[k]*2>n){
printf("-1\n");
}else{
f(0,q[k]);
for(int i=0;i<n-b[k]*2;i++){
printf("(");
}printf("\n");
}
}
}
标签:Week,100005,Winter,int,SMU,贡献,2024
From: https://www.cnblogs.com/ptlks/p/18019188