三道金组比较容易的题目。。
2058
首先交换次数就是逆序对数，因为只能交换相邻的两数
先对原序列找逆序对数
用树状数组nlogn求出
然后O(n)依次求出其循环序列的逆序对数
比如 3 5 4 2 1
循环之后相对应的位置变成
2 4 3 1 5
表示第一个数到位置2，第二个数到位置4，第三个数到位置1 etc.
那么依次减一的那些数的逆序对数是不变的。只有1变成5的那个增加或减少了逆序对数
由于5是序列里最大的数，设其所在位置为i，因此增加了n-i对，减少了i-1对
这样总复杂度就是nlogn的
记得开Long long
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
using namespace std;
struct node{
int v,id;
}a[];
LL tot,ans,p[];
int n;
bool cmp(node a, node b){
return a.v<b.v;
}
void add(int x){
while (x<=n){
p[x]++;
x+=x&-x;
}
}
LL sum(int x){
LL ret=;
while (x){
ret+=p[x];
x-=x&-x;
}return ret;
}
int main(){
scanf("%d", &n);
; i<=n; i++) scanf(;
tot=;
; i<=n; i++){
add(a[i].v);
tot+=(LL)i-sum(a[i].v);
}
sort(a+,a++n,cmp);
ans=tot;
; i<=n; i++){
);
tot+=(LL)del;
ans=min(ans,tot);
}
printf("%lld\n", ans);
;
}
2059
单调队列DP，降复杂度为O(NK)
分n阶段进行单调队列的优化dp
设dis=a[i].x-a[i-1].x
f[i][k]=cost[i]*k+min{f[i-1][j]-cost[i]*j+dis*j*j};
显然f[i][k]只与f[i-1][k]有关所以省略一维，并且先插入队列(此时为f[i-1][k]的值)，然后再更新为f[i][k]
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
using namespace std;
;
struct node{
int x,f;
LL c;
}a[maxn];
struct que{
int v;
LL val;
}q[maxn*];
int K,end,n;
LL f[maxn];
bool cmp(node a, node b){
return a.x<b.x;
}
int main(){
scanf("%d%d%d", &K, &end, &n);
; i<=n; i++) scanf("%d%d%lld", &a[i].x, &a[i].f, &a[i].c);
sort(a+,a++n,cmp);
memset(f,0x3f3f3f3f,sizeof(f));
f[]=;
; i<=n; i++){
, tail=;
LL dis=a[i].x-a[i-].x;
q[tail].v=,q[tail].val=,tail++;
; j<=K; j++){
LL now=f[j]-(LL)j*a[i].c+dis*(LL)j*(LL)j;
].val>=now) tail--;
q[tail].v=j, q[tail].val=now, tail++;
while (head<tail && q[head].v+a[i].f<j) head++;
f[j]=q[head].val+(LL)j*a[i].c;
}
}
printf("%lld\n", f[K]+(LL)K*(LL)K*(LL)(end-a[n].x));
;
}
2060
树形dp的入门水题。。
f[u]表示选u的最大值
g[u]表示不选u的最大值
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
;
struct node{
int to,next;
}e[maxn];
int g[maxn],f[maxn],n,head[maxn],tot,u,v;
void insert(int u, int v){
e[++tot].to=v; e[tot].next=head[u]; head[u]=tot;
}
void dfs(int x, int fa){
g[x]=; f[x]=;
; i=e[i].next){
int v=e[i].to;
if (v==fa) continue;
dfs(v,x);
g[x]+=max(g[v],f[v]);
f[x]+=g[v];
}
}
int main(){
scanf("%d", &n);
tot=; memset(head,-,sizeof(head));
; i<n; i++){
scanf("%d%d", &u, &v);
insert(u,v); insert(v,u);
}
dfs(,);
printf(],f[]));
;
}