最近在学动态规划，看到$vjudge$上这套题感觉挺有意思的。
| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 19/19 | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
求一个序列的最大$m$段非空子段和。
解题思路
设$g[i][j]$表示前$i$个元素中选取$j$个段，且必包含第$i$个元素的最大值。
设$f[i][j]$表示前$i$个元素中选取$j$个段，且不必包含第$i$个元素的最大值。则有：
$g[i][j]=max(g[i-1][j],f[i-1][j-1])+a[i]$
$f[i][j]=max(g[i-1][j],f[i-1][j])$答案即为$f[n][m]$。
滚动数组优化掉第一维即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;
int n,m,a[N];
ll g[N],f[N];
int min(int a,int b){return a>b?b:a;}
ll max(ll a,ll b){return a>b?a:b;}
int main(){
int i,j;
while(~scanf("%d%d",&m,&n)){
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)g[i]=f[i]=-1e18;
for(i=1;i<=n;i++)
for(j=min(i,m);j;j--){
g[j]=max(g[j],f[j-1])+a[i];
f[j]=max(f[j],g[j]);
}
printf("%lld\n",f[m]);
}
return 0;
}
B
题目描述
给定一段个数$n$为奇数的序列，其中有一个数字出现了至少$\frac {n+1}2$次，问这个数是多少。
$1\leq n\leq999999$，$a[i]∈[-2^{31},2^{31}-1]$。
解题思路
用$map$可以水过，但可以用一种更巧妙的思路做出来。
显然，如果两个数不相等，那么删掉这两个数之后剩下的数仍然满足题目要求。所以可以用一个$cnt$表示当前数出现的净次数（删掉和它不等的相同个数的数），当$cnt=0$时更新答案，也就是说答案在结束的时候必须满足它对应的$cnt\neq0$。所以最后的答案必然是所求。
AC代码-map
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::map<int,int>m;
int main(){
int i,n,a,ans;
while(~scanf("%d",&n)){
m.clear();
for(i=0;i<n;i++){
scanf("%d",&a);
m[a]++;
if(m[a]>=(n+1)/2)ans=a;
}
printf("%d\n",ans);
}
return 0;
}AC代码-递推
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(){
int i,n,cnt,a,ans;
while(~scanf("%d",&n)){
cnt=0;
for(i=0;i<n;i++){
scanf("%d",&a);
if(!cnt)cnt=1,ans=a;
else cnt+=a==ans?1:-1;
}
printf("%d\n",ans);
}
return 0;
}
C
题目描述
给定一些种类的长方体的长宽高，它们有任意多个、可任意摆放（指任意方式竖立），问当保证下一层的长宽严格大于上一层的长宽的时候，可以摞起来的最大高度。
解题思路
数据超级水，直接添加所有的长宽高组合，以长为关键词排序，从上到下递推即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
struct Box{
int x,y,z;
bool operator<(const Box&a)const{return x>a.x;}
}a[N];
int n,tot,dp[N],b[4];
void add(int x,int y,int z){a[tot++]={x,y,z};}
int main(){
int i,j,k,l,ans,cas=0;
while(~scanf("%d",&n)&&n){
tot=ans=0;
memset(dp,0,sizeof(dp));
for(l=0;l<n;l++){
scanf("%d%d%d",&b[0],&b[1],&b[2]);
for(i=0;i<3;i++)for(j=0;j<3;j++)for(k=0;k<3;k++)
if(i!=j&&i!=k&&j!=k)add(b[i],b[j],b[k]);
}
sort(a,a+tot);
for(i=0;i<tot;i++){
for(j=0;j<i;j++)if(a[i].x<a[j].x&&a[i].y<a[j].y)dp[i]=max(dp[i],dp[j]);
dp[i]+=a[i].z;
ans=max(ans,dp[i]);
}
printf("Case %d: maximum height = %d\n",++cas,ans);
}
return 0;
}
D
题目描述
现在摆在面前一堆作业和$DDL$，并知道每个作业需要的时间，求使得超出$DDL$的时间的总和最小的方案。如果有多种，输出作业名字典序最小的那一种。数据保证给定的顺序符合作业名字典序。
解题思路
一上来想了个贪心，哗哗哗写出来了兴高采烈地交上了。
然后获得了$WA$。
WA代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
struct ddl{
char a[110];
int d,c;
bool operator<(const ddl&p)const{return d<p.d||(d==p.d&&strcmp(a,p.a)<0);}
}a[16];
int main(){
int i,n;scanf("%*d");
while(~scanf("%d",&n)){
for(i=0;i<n;i++)scanf("%s%d%d",a[i].a,&a[i].d,&a[i].c);
sort(a,a+n);
int ans=0,time=0;
for(i=0;i<n;i++){
time+=a[i].c;
if(time>a[i].d)ans+=time-a[i].d;
}
printf("%d\n",ans);
for(i=0;i<n;i++)printf("%s\n",a[i].a);
}
return 0;
}
然后找到了下面这组数据：
$1$
$5$
$A$ $10$ $2$
$B$ $2$ $8$
$C$ $10$ $1$
$D$ $9$ $3$
$E$ $2$ $1$$emmmm$，贪心确实行不通。
那咋办呢？一看数据范围，这不赤裸裸地提示状压嘛！
从下到上递推，记录一下每一个状态是由哪里转移过来的，然后输出试试？诶，$A$了！
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
struct ddl{
char a[110];
int d,c;
}a[16];
struct state{
int t,pre,v;//走到这一步的时间，总消耗
}dp[1<<15];
int seq[16];
int f(int x){
int cnt=0;
while(x)x>>=1,cnt++;
return cnt-1;
}
int main(){
int i,j,n;scanf("%*d");
while(~scanf("%d",&n)){
for(i=0;i<n;i++)scanf("%s%d%d",a[i].a,&a[i].d,&a[i].c);
for(i=1;i<(1<<n);i++)dp[i].v=1e9;
for(i=0;i<(1<<n);i++){
for(j=0;j<n;j++){
if((i&(1<<j))==0){
int tar=i+(1<<j),t=max(0,dp[i].t+a[j].c-a[j].d);
if(dp[tar].v>dp[i].v+t){
dp[tar].v=dp[i].v+t;
dp[tar].t=dp[i].t+a[j].c;
dp[tar].pre=i;
}
}
}
}
printf("%d\n",dp[(1<<n)-1].v);
int p=n;
i=(1<<n)-1;
while(n){
seq[--n]=f(i^dp[i].pre);
i=dp[i].pre;
}
for(i=0;i<p;i++)printf("%s\n",a[seq[i]].a);
}
return 0;
}
但似乎事情不太对。这个$pre$定下来定的毫无道理啊，不能一定满足字典序最小。
有了！从上向下递推，再$dfs$一遍找出最优解！
也许只是数据比较水，所以$AC$了也不一定就是对的呢。
AC代码-REAL
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;
struct ddl{
char a[110];
int d,c;
}a[16];
struct state{
int t,v;//走到这一步的时间，总消耗
}dp[1<<15];
int seq[16],tmp[16],n,FLAG;
void dfs(int p,int dep){
int i;
if(!p){
int flag=0;
if(!FLAG){
FLAG=flag=1;
}else for(i=n-1;i>=0;i--){
int cmp=strcmp(a[tmp[i]].a,a[seq[i]].a);
if(cmp<0){
flag=1;
break;
}else if(cmp)break;
}
if(flag)for(i=0;i<n;i++)seq[i]=tmp[i];
return;
}
for(i=0;i<n;i++){
if(p&(1<<i)){
int tar=p-(1<<i),t=max(0,dp[tar].t+a[i].c-a[i].d);
if(dp[p].v==dp[tar].v+t){
tmp[dep]=i;
dfs(tar,dep+1);
}
}
}
}
int main(){
int i,j;scanf("%*d");
while(~scanf("%d",&n)){
FLAG=0;
for(i=0;i<n;i++)scanf("%s%d%d",a[i].a,&a[i].d,&a[i].c);
for(i=1;i<(1<<n);i++)dp[i].v=1e9;
for(i=0;i<(1<<n);i++){
for(j=0;j<n;j++){
if(i&(1<<j)){
int tar=i-(1<<j),t=max(0,dp[tar].t+a[j].c-a[j].d);
if(dp[i].v>dp[tar].v+t){
dp[i].v=dp[tar].v+t;
dp[i].t=dp[tar].t+a[j].c;
}
}
}
}
printf("%d\n",dp[(1<<n)-1].v);
dfs((1<<n)-1,0);
for(i=n-1;i>=0;i--)printf("%s\n",a[seq[i]].a);
}
return 0;
}
E
题目描述
给定一个整数序列，求其严格单调递增子序列（可为空）的最大和。
解题思路
从前往后递推即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int n,a[N];
long long ans,dp[N];
int main(){
int i,j;
while(~scanf("%d",&n)&&n){
ans=0;
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++){
dp[i]=a[i];
for(j=0;j<i;j++)if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+a[i]);
ans=max(ans,dp[i]);
}
printf("%lld\n",ans);
}
return 0;
}
F
题目描述
给定一堆物品的总重，以及构成这堆物品的所有可能元素的价值和重量，判断存不存在一种方案使得给定元素构成这堆物品。如果存在，输出总价值的下确界。
解题思路
完全背包，压缩到一维即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int t,n,e,f,v[N],w[N],dp[10010];
int main(){
int i,j;
scanf("%d",&t);
while(t--){
scanf("%d%d",&e,&f);
f-=e;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d",&v[i],&w[i]);
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(i=0;i<n;i++)
for(j=w[i];j<=f;j++)
dp[j]=std::min(dp[j],dp[j-w[i]]+v[i]);
if(dp[f]<1e9)printf("The minimum amount of money in the piggy-bank is %d.\n",dp[f]);
else printf("This is impossible.\n");
}
return 0;
}
G
题目描述
天上正在掉馅饼，给定掉馅饼的坐标（一维）和时间，初始位置给定，求能够接到的最大馅饼数。
解题思路
两种递推思路，从前往后，从后往前。从后往前的比较好写，不用判特殊情况。滚动掉一维即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int n,x,t,a[12][N],dp[2][14];
int main(){
int i,j;
while(~scanf("%d",&n)&&n){
int mx=0;
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
for(i=0;i<n;i++)scanf("%d%d",&x,&t),a[x+1][t]++,mx=max(mx,t);
for(i=mx;i>=0;i--)
for(j=1;j<12;j++)
dp[i&1][j]=max(max(dp[(i+1)&1][j-1],dp[(i+1)&1][j]),dp[(i+1)&1][j+1])+a[j][i];
printf("%d\n",dp[0][6]);
}
return 0;
}
H
题目描述
有一列人，花费$a[i]$时间可以消除第$i$个人，花费$b[i]$时间可以消除第$i$和第$i+1$个人。求最短用时，求最终时刻的$HH:MM:SS$ $am|pm$表示。
解题思路
直接暴力递推即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int n,k,a[N],b[N],dp[N];
int main(){
int i;
scanf("%*d");
while(~scanf("%d",&k)){
for(i=1;i<=k;i++)scanf("%d",&a[i]);
for(i=2;i<=k;i++)scanf("%d",&b[i]);
dp[0]=0;dp[1]=a[1];
for(i=2;i<=k;i++)dp[i]=min(dp[i-2]+b[i],dp[i-1]+a[i]);
int h=8,m=0,s=dp[k];
if(s>=60)m+=s/60,s%=60;
if(m>=60)h+=m/60,m%=60;
printf("%02d:%02d:%02d %s\n",(h-1)%12+1,m,s,h>12?"pm":"am");
}
return 0;
}
I
题目描述
求一个序列的非严格下降子列的最小个数。
解题思路
也就是求严格上升子列长度。$O(log n)$解决。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
int a,dp[N],len;
int main(){
int i,n;
while(~scanf("%d",&n)){
scanf("%d",&dp[0]);
len=1;
for(i=1;i<n;i++){
scanf("%d",&a);
if(a>dp[len-1])dp[len++]=a;
else{
int p=upper_bound(dp,dp+len,a)-dp;
if(dp[p]>a)dp[p]=a;
}
}
printf("%d\n",len);
memset(dp,0,sizeof(int)*n);
}
return 0;
}
J
题目描述
给一些老鼠的速度和质量，求最长的子序列保证老鼠的质量严格递增而速度严格递减，输出方案。
解题思路
对质量排序后递推并记录从哪里递推得到的，最后递归输出。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
struct mouse{
int a,b,i;
bool operator<(const mouse&p)const{return a<p.a;}
}a[N];
int len[N],last[N],mx,temp;
void print(int x){
if(!x)return;
print(last[x]);
printf("%d\n",x);
}
int main(){
int j,i=0,k;
while(~scanf("%d%d",&a[i].a,&a[i].b)){
a[i].i=i+1;
i++;
}
sort(a,a+i);
for(j=0;j<i;j++){
len[j]=1;
for(k=0;k<j;k++){
if(a[k].a<a[j].a&&a[k].b>a[j].b&&len[k]+1>len[j]){
len[j]=len[k]+1;
last[a[j].i]=a[k].i;
}
}
if(len[j]>mx){
mx=len[j];
temp=a[j].i;
}
}
printf("%d\n",mx);
print(temp);
return 0;
}
K
题目描述
给一些人的两种特性$d$和$p$，选择给定数量个人，使得这些人$d$总和$D$与$p$总和$P$之差的绝对值$|D-P|$最小的情况下，$D+P$最大，输出$|D-P|$，$D+P$，并按上升序输出选择人的序号。
解题思路
一个个人选择，$dp[i][j]$表示选了$i$个人，其$D-P=j$（没有绝对值）的情况下，$D+P$的最大值。记录下选了$i$个人、每个$j$对应的最优解对应的人的编号$path[i][j]$，每次枚举每一个人，如果在这个条件下没有加入则可以加入这个人。
由于不能加绝对值，需要加一个$offset$调整。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
int n,m,d[N],p[N],v[N],s[N];
int f[M][M*M*2],path[M][M*M*2];
int sel(int num,int val,int now){
while(num&&path[num][val]!=now)val-=v[path[num][val]],num--;
return num;
}
int seq[M];
int main(){
int i,j,k,cas=0;
while(~scanf("%d%d",&n,&m)&&n|m){
cas++;
memset(f,-1,sizeof(f));
int offset=m*M;
f[0][offset]=0;
for(i=1;i<=n;i++)
scanf("%d%d",&d[i],&p[i]),v[i]=d[i]-p[i],s[i]=d[i]+p[i];
for(i=1;i<=m;i++){
for(j=0;j<=offset*2;j++){
if(f[i-1][j]<0)continue;
for(k=1;k<=n;k++){
if(f[i-1][j]+s[k]>f[i][j+v[k]]&&!sel(i-1,j,k)){
path[i][j+v[k]]=k;
f[i][j+v[k]]=f[i-1][j]+s[k];
}
}
}
}
for(i=0;i<=offset;i++)if(f[m][offset+i]>=0||f[m][offset-i]>=0)break;
int ans=f[m][offset+i]>f[m][offset-i]?offset+i:offset-i;
printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",cas,(ans-offset+f[m][ans])/2,(-ans+offset+f[m][ans])/2);
for(i=m;i;i--)seq[i]=path[i][ans],ans-=v[path[i][ans]];
sort(seq+1,seq+m+1);
for(i=1;i<=m;i++)printf(" %d",seq[i]);
printf("\n\n");
}
return 0;
}
L
题目描述
求最长公共子序列。
解题思路
裸题，非常裸。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char a[N],b[N];
int dp[N][N];
int main(){
int i,j;
while(~scanf("%s%s",a+1,b+1)){
int l=strlen(a+1),L=strlen(b+1);
for(i=1;i<=l;i++){
for(j=1;i<=L;j++){
if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
printf("%d\n",dp[l][L]);
memset(dp,0,sizeof(dp));
}
return 0;
}
M
题目描述
有一堆高度不同、起终不同的板子，一个人，这个人要到地上，求最短时间。
这人很神奇，下落、平移的速度相同。但下落高度不能超过给定值，否则会摔死。数据保证一定有解。
解题思路
纯搜索$T$掉了，记忆化搜索就可以了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using namespace std;
struct ck{
int x[2],h;
bool operator <(const ck&a)const{return h>a.h;}
}a[N];
int t,n,x,y,mx;
int dp[2][1010];
int dfs(int now,int dir){
if(dp[dir][now])return dp[dir][now];
int i,x=a[now].x[dir];
for(i=now+1;i<=n+1&&a[now].h-a[i].h<=mx;i++){
if(i==n+1)return dp[dir][now]=a[now].h;
if(x>=a[i].x[0]&&x<=a[i].x[1])return dp[dir][now]+=min(x-a[i].x[0]+dfs(i,0),a[i].x[1]-x+dfs(i,1))+a[now].h-a[i].h;
}
return dp[dir][now]=1e8;
}
int main(){
int i;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&n,&x,&y,&mx);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].x[0],&a[i].x[1],&a[i].h);
a[0].x[0]=a[0].x[1]=x;a[0].h=y;
sort(a+1,a+n+1);
printf("%d\n",dfs(0,1));
}
return 0;
}
N
题目描述
求最长严格上升子序列。
解题思路
又是一道裸题。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
int n,a,len,dp[1010];
int main(){
int i;
scanf("%d",&n);
scanf("%d",&a);dp[len++]=a;
for(i=1;i<n;i++){
scanf("%d",&a);
if(a>dp[len-1])dp[len++]=a;
else{
int p=upper_bound(dp,dp+len,a)-dp;
dp[p]=min(dp[p],a);
}
}
printf("%d",len);
return 0;
}
O
题目描述
给定一些食物，其价格与时间成正比，给定系数。每次必须且只能从头或尾取，求最大价格和。
解题思路
区间$DP$，从最后一个取出递推到开头，$dp[i][j]$表示$i,j$之间所有元素最后取出的最大价值和。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[N],n,dp[N][N];
int main(){
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]),dp[i][i]=a[i]*n;
for(i=1;i<n;i++)
for(j=0;j+i<n;j++)
dp[j][j+i]=std::max(dp[j][j+i-1]+a[j+i]*(n-i),dp[j+1][j+i]+a[j]*(n-i));
printf("%d",dp[0][n-1]);
return 0;
}
P
题目描述
一个老鼠在一个由奶酪组成的格子图中走动，每次可以上下走动$1$到$k$个格子，并吃掉这个格子里的奶酪。要求每次吃的奶酪都比上次大，终点任选，求可以吃到的奶酪的最大和。
解题思路
记忆化搜索，每次可以向四个方向走一定距离。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int a[N][N],n,k,dp[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int dfs(int x,int y){
if(~dp[x][y])return dp[x][y];
dp[x][y]=a[x][y];
int i,j,p,q,mx=0;
for(i=0;i<4;i++){
for(j=1;j<=k;j++){
p=x+dx[i]*j;
q=y+dy[i]*j;
if(p>=0&&q>=0&&p<n&&q<n&&a[p][q]>a[x][y]){
dfs(p,q);
if(dp[p][q]>mx)mx=dp[p][q];
}
}
}
return dp[x][y]+=mx;
}
int main(){
int i,j;
while(~scanf("%d%d",&n,&k)&&~n&&~k){
memset(dp,-1,sizeof(dp));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("%d\n",dfs(0,0));
}
return 0;
}
Q
题目描述
求最大关于反对角线对称的子矩阵。
解题思路
想法是从右上角枚举到左下角，每次扩展一定范围并判断是否合理（能否对称），但程序很慢，跑了$2000ms$还多。
看到有人跑了不到$200ms$，不知道是什么方法。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n,dp[N][N];
char a[N][N];
int main(){
int i,j,k;
while(~scanf("%d",&n)&&n){
int ans=0;
for(i=0;i<n;i++)scanf("%s",a[i]);
for(i=0;i<n;i++){
for(j=n-1;j>=0;j--){
dp[i][j]=1;
if(i&&j<n-1){
for(k=1;k<=dp[i-1][j+1];k++){
if(a[i-k][j]==a[i][j+k])dp[i][j]++;
else break;
}
}
if(ans<dp[i][j])ans=dp[i][j];
}
}
printf("%d\n",ans);
}
return 0;
}
R
题目描述
给一段挤奶时间的开始和结束点，每次挤奶的产量，求最大总产量。两次挤奶需要间隔一定时间。
解题思路
对时间段关于结束时间递减排序，从前向后递推即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
struct interval{
int b,e,v;
bool operator<(const interval&a)const{return e<a.e;}
}a[N];
int dp[N];
int n,m,r;
int main(){
int i,j,ans=0;
scanf("%d%d%d",&n,&m,&r);
for(i=0;i<m;i++)scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].v);
sort(a,a+m);
for(i=0;i<m;i++){
dp[i]=0;
for(j=0;j<i;j++)if(a[j].e+r<=a[i].b)dp[i]=max(dp[i],dp[j]);
dp[i]+=a[i].v;
ans=max(ans,dp[i]);
}
printf("%d",ans);
return 0;
}
S
题目描述
给定一段序列，增加或减少其中的某些元素的值，使得最终序列非严格单调递增或递减。求最终序列和原序列每一个元素差值绝对值的和的最小值。$1\leq n\leq2000$，序列中的数保证$0\leq a[i]\leq 10^9$。
解题思路
数很大，需要离散化，$dp[i][j]$表示枚举到第$i$个数且让它变成第$j$小/大的数$b[j]$时的贡献，因为保证序列单调，有$dp[i][j]=min(dp[i-1][k])(k∈[0,j])+|a[i]-b[j]|$。其中$min(dp[i-1][k])(k∈[0,j])$可以实时更新。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
int n;
int a[N],b[N],dp[N][N],ans=1e9;
int f(int x){return x>0?x:-x;}
int cmp(int x,int y){return x>y;}
void solve(){
int i,j;
memset(dp,0x3f,sizeof(dp));
for(i=0;i<n;i++)dp[0][i]=f(a[0]-b[i]);
for(i=1;i<n;i++){
int mn=1e9;
for(j=0;j<n;j++){
mn=min(mn,dp[i-1][j]);
dp[i][j]=mn+f(a[i]-b[j]);
}
}
for(i=0;i<n;i++)ans=min(ans,dp[n-1][i]);
}
int main(){
int i;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b,b+n);solve();
sort(b,b+n,cmp);solve();
printf("%d",ans);
return 0;
}