由于题目比较多,就只发一下题目意思和思路+代码,最后总结一下.
A - Max Sum Plus Plus
Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x≤ 32767). We define a function sum(i, j) = S i + ... + S j (1 ≤ i ≤ j ≤ n).
Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i 1, j 1) + sum(i2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) maximal (i x ≤ i y ≤ j x or i x ≤ j y ≤ j x is not allowed).
But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i x, j x)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S 1, S 2, S 3 ... S n.
Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3 Sample Output
6
8
Hint
Huge input, scanf and dynamic programming is recommended. 题目大意:最大m子段和模板题.
题目思路:
找出状态转移方程 dp[i][j] 表示 前i个数 分成j段可以获得到的最大值 那么:
dp[i][j]=max(dp[i-1][j-1]+num[j],dp[k][j]) 表示第i个数要么 与 自己合为一段 要么与小于当前的i合为一段 之前写过这个题解:
https://blog.csdn.net/qq_43857314/article/details/88970904
B - Ignatius and the Princess IV
给你n个数字，你需要找出出现至少(n+1)/2次的数字 现在需要你找出这个数字是多少？
Input
本题包含多组数据： 每组数据包含两行。 第一行一个数字N(1<=N<=999999) ，保证N为奇数。 第二行为N个用空格隔开的整数。 The input is terminated by the end of file.
Output
For each test case, you have to output only one line which contains the special number you have found.
Sample Input
5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1 Sample Output
3
5
1 提示
如果不排序，怎么做？
题解思路:因为N一定为奇数 所以绝为会有一个奇数个数出现,用这个去判断 ,与上一个数字相同就-,不同就+:
#include<bits/stdc++.h>
#define ll long long
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e6+1000;
const int INF=1e9+7;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m;
ll cot[maxn];
bool vis[maxn];
ll num[maxn];
int main()
{
while(~scanf("%lld",&n))
{
memset(cot,0,sizeof(cot));
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
num[i]=read();
for(int i=1;i<=n;i++)
{
cot[num[i]]++;
if(cot[num[i]]>=(n+1)/2&&!vis[num[i]])
{
printf("%lld",num[i]);
vis[num[i]]=true;
}
}
printf("\n");
}
return 0;
} C - Monkey and Banana
一组研究人员正在设计一项实验，以测试猴子的智商。他们将挂香蕉在建筑物的屋顶，同时，提供一些砖块给这些猴子。如果猴子足够聪明，它应当能够通过合理的放置一些砖块建立一个塔，并爬上去吃他们最喜欢的香蕉。
研究人员有n种类型的砖块，每种类型的砖块都有无限个。第i块砖块的长宽高分别用xi，yi，zi来表示。 同时，由于砖块是可以旋转的，每个砖块的3条边可以组成6种不同的长宽高。
在构建塔时，当且仅当A砖块的长和宽都分别小于B砖块的长和宽时，A砖块才能放到B砖块的上面，因为必须留有一些空间让猴子来踩。
你的任务是编写一个程序，计算猴子们最高可以堆出的砖块们的高度。
Input
输入文件包含多组测试数据。
每个测试用例的第一行包含一个整数n，代表不同种类的砖块数目。n<=30.
接下来n行，每行3个数，分别表示砖块的长宽高。
当n= 0的时候，无需输出任何答案，测试结束。
Output
对于每组测试数据，输出最大高度。格式：Case 第几组数据: maximum height = 最大高度
Sample Input
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
题目思路:首先每个砖块只有6种形态直接全存数组中,然后采用最长公共子序列的方法去判断,注意要实现排序,尽可能的让大的在下面:
#include<bits/stdc++.h>
#define ll long long
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e5+1000;
const int INF=1e9+7;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m;
ll dp[2000];
struct node{
ll l,w,h;
}brick[2000];
bool cmp(node a,node b)
{
if(a.l==b.l) return a.w>b.w;
return a.l>b.l;
}
int main()
{
int T;int cas=0;
while(~scanf("%lld",&n)&&n)
{
ll cnt=0;
for(int i=1;i<=n;i++)
{
ll x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
brick[++cnt].l=x;brick[cnt].w=y;brick[cnt].h=z;
brick[++cnt].l=z;brick[cnt].w=y;brick[cnt].h=x;
brick[++cnt].l=y;brick[cnt].w=x;brick[cnt].h=z;
brick[++cnt].l=y;brick[cnt].w=z;brick[cnt].h=x;
brick[++cnt].l=z;brick[cnt].w=x;brick[cnt].h=y;
brick[++cnt].l=x;brick[cnt].w=z;brick[cnt].h=y;
}
sort(brick+1,brick+cnt+1,cmp);
ll ans=-INF;
for(int i=1;i<=cnt;i++)
{
dp[i]=0;
for(int k=1;k<i;k++)
{
if(brick[i].l<brick[k].l&&brick[i].w<brick[k].w)
{
dp[i]=max(dp[i],dp[k]);
}
}
dp[i]+=brick[i].h;
ans=max(dp[i],ans);
}
printf("Case %d: maximum height = %lld\n",++cas,ans);
}
return 0;
}
D - Doing Homework
Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework).
Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.
Output
For each test case, you should output the smallest total reduced score, then give out the order of the subjects, one subject in a line. If there are more than one orders, you should output the alphabet smallest one.
Sample Input
2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3 题目大意:每一门科目有 截止时间,昨晚该门课程需要多少时间,如果做完该们课程超出该们的截止时间就会扣分,问最少扣多少分?
题解思路:
这是一个状压dp,首先所有作业必须全完成 状态为(1111...n个)2,我们遍历每一个状态从小到大.每一个状态扣得分我们就可以知道
对于每一个状态 我们需要知道完成第j门课程之前的最优状态,来推出当前状态,总而言之 对于每一种状态而言 我们遍历他所有的课程 就得到了这个状态的最优顺序
代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=1e9;
const int maxn=(1<<15)+10;
int n,m;
int dp[maxn];
int t[maxn],dt[50],ti[50];
int pre[maxn];
char str[20][110];
void print(int x)
{
ll temp=1<<pre[x];
if(!x) return;
print(x-temp);
printf("%s\n",str[pre[x]]);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(pre,0,sizeof(pre));
memset(t,0,sizeof(t));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s%d%d",&str[i],&dt[i],&ti[i]);
for(int i=1;i<(1<<n);i++)
{
dp[i]=INF;
for(int j=n;j>=1;j--)
{
int tmp=1<<(j-1);
if(!(i&tmp)) continue;//这个状态没有第J门课
int temp=i-tmp;//表示没有完成作业j之前的状态
int up=t[temp]+ti[j]-dt[j];
if(up<0) up=0;
if(dp[i]>dp[temp]+up)
{
dp[i]=dp[temp]+up;
pre[i]=j-1;
t[i]=t[temp]+ti[j];
}
}
}
int temp=(1<<n)-1;
printf("%lld\n",dp[temp]);
print(temp);
}
return 0;
}
E - Super Jumping! Jumping! Jumping!
zh成功的在他人的帮助下获得了与小姐姐约会的机会，同时也不用担心被非“川大”的女票发现了，可是如何选择和哪些小姐姐约会呢？zh希望自己可以循序渐进，同时希望挑战自己的极限，我们假定每个小姐姐有一个“攻略难度值”
从攻略成功第一个小姐姐开始，zh希望每下一个需要攻略的小姐姐难度更高，同时又希望攻略难度值之和最大，好了，现在小姐姐们排成一排，zh只能从左往右开始攻略，请你帮助他找到最大的攻略难度和
Input
多组输入，每组数据占一行，每行一个整数n表示小姐姐个数，接着n个数a_1, a_2, ..., a_n表示第i个的小姐姐攻略难度 (a_i在32位有符号整型范围内)，n = 0表示输入结束 (0 <= n <= 1000)。 Output
一个数，最大攻略和 Sample Input
3 1 3 2
4 1 2 3 4
4 3 3 2 1
0 Sample Output
4
10
3 题解思路:类似最长公共子序列.. 代码就不附了 水题.
F - Piggy-Bank
在 ACM 能够开展之前，必须准备预算，并获得必要的财力支持。该活动的主要收入来自于 Irreversibly Bound Money (IBM)。思路很简单。任何时候，某位 ACM 会员有少量的钱时，他将所有的硬币投入到小猪储钱罐中。这个过程不可逆，因为只有把小猪储钱罐打碎才能取出硬币。在足够长的时间之后，小猪储钱罐中有了足够的现金，用于支付 ACM 活动所需的花费。
但是，小猪储钱罐存在一个大的问题，即无法确定其中有多少钱。因此，我们可能在打碎小猪储钱罐之后，发现里面的钱不够。显然，我们希望避免这种不愉快的情况。唯一的可能是，称一下小猪储钱罐的重量，并尝试猜测里面的有多少硬币。假定我们能够精确判断小猪储钱罐的重量，并且我们也知道给定币种的所有硬币的重量。那么，我们可以保证小猪储钱罐中最少有多少钱。
你的任务是找出最差的情形，即判断小猪储钱罐中的硬币最少有多少钱。我们需要你的帮助。不能再贸然打碎小猪储钱罐了！
输入
输入包含 T 组测试数据。输入文件的第一行，给出了 T 的值。
对于每组测试数据，第一行包含 E 和 F 两个整数，它们表示空的小猪储钱罐的重量，以及装有硬币的小猪储钱罐的重量。两个重量的计量单位都是 g (克)。小猪储钱罐的重量不会超过 10 kg (千克)，即 1 <= E <= F <= 10000 。每组测试数据的第二行，有一个整数 N (1 <= N <= 500)，提供了给定币种的不同硬币有多少种。接下来的 N 行，每行指定一种硬币类型，每行包含两个整数 P 和 W (1 <= P <= 50000，1 <= W <=10000)。P 是硬币的金额 (货币计量单位)；W 是它的重量，以 g (克) 为计量单位。
输出
对于每组测试数据，打印一行输出。每行必须包含句子 “The minimum amount of money in the piggy-bank is X.” 其中，X 表示对于给定总重量的硬币，所能得到的最少金额。如果无法恰好得到给定的重量，则打印一行 “This is impossible.” 。
示例输入
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
示例输出
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
题解思路:
多重背包 与普通背包类似,因为他的物品无限,所以枚举重量的时候,应该从小到大枚举.
#include<bits/stdc++.h>
#define ll long long
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e5+1000;
const int INF=1e9+7;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m,e,f;
ll dp[10005];
ll v[505],w[505];
int main()
{
int T;int cas=0;
scanf("%d",&T);
while(T--)
{
memset(dp,INF,sizeof(dp));
scanf("%lld%lld",&e,&f);
f-=e;scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&v[i],&w[i]);
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int k=w[i];k<=f;k++)
dp[k]=min(dp[k],dp[k-w[i]]+v[i]);
}
if(dp[f]<INF)
printf("The minimum amount of money in the piggy-bank is %lld.\n",dp[f]);
else
printf("This is impossible.\n");
}
return 0;
}
G - 免费馅饼
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：
为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）
Input
输入数据有多组。每组数据的第一行为以正整数n(0<n<100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
Output
每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0 Sample Output
4 题解思路:二维数组存下在哪个位置什么时间 掉落多少,然后就开始二层for枚举就可以了,注意他的开始条件确定所以,从下往上比较好dp
()
{
while(~scanf("%lld",&n)&&n)
{
ll maxl=-INF;
memset(mp,0,sizeof(mp));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
ll x,y;
x=read();y=read();
x+=1;
mp[y][x]++;// firtst :the order of minute
maxl=max(y,maxl);
}
for(int i=maxl;i>=1;i--)
for(int k=1;k<=11;k++)
dp[i][k]=max(dp[i+1][k],max(dp[i+1][k-1],dp[i+1][k+1]))+mp[i][k];
/*for(int i=1;i<=maxl;i++)
{
for(int k=1;k<=11;k++)
printf("%lld ",dp[i][k]);
printf("\n");
}*/
printf("%lld\n",max(dp[1][6],max(dp[1][5],dp[1][7])));
}
return 0;
} H - Tickets
现在有n个人要买电影票，如果知道每个人单独买票花费的时间，还有和前一个人一起买花费的时间，问最少花多长时间可以全部买完票。
Input
给出 N(1<=N<=10)，表示有N组样例 给出K (1<=K<=2000)，表示有K个人买票.. 给出K个数表示这个人单独买票会花的时间..保证每个数 (0s<=Si<=25s) 给出K-1个数，表示这个人和前面那个人一起买票会花的时间..保证每个数 (0s<=Si<=50s)
Output
对于每一组数据，你需要给出电影院售票结束的时间，售票开始的时间为 08:00:00 am. 时间格式为： HH:MM:SS am|pm. 具体看样例输出
Sample Input
2
2
20 25
40
1
8 Sample Output
08:00:40 am
08:00:08 am 题解思路:这题有点坑我,按一维推的,推不出来,所以应该用二维来开 第二维表示 表示单独买 还是一起买
#include<bits/stdc++.h>
#define ll long long
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e5+1000;
const int INF=1e9+7;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m;
ll dp[2005][2];// I first
ll num[2005];
ll temp[2005];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
for(int i=2;i<=n;i++) scanf("%lld",&temp[i]);
dp[1][0]=num[1];
dp[1][1]=num[1];
for(int i=2;i<=n;i++)
{
dp[i][0]=min(dp[i-1][1],dp[i-1][0])+num[i];
dp[i][1]=min(dp[i-2][0],dp[i-2][1])+temp[i];
}
ll res=min(dp[n][1],dp[n][0]);
// printf("%lld\n",res);
ll h=8,m=0,s=0;
ll ans=8*60*60;
ans+=res;
s=ans%60;
ans/=60;
m=ans%60;
ans/=60;
h=ans%60;
ans/=60;
if(h>12)
printf("%02lld:%02lld:%02lld pm\n",h-12,m%60,s);
else
printf("%02lld:%02lld:%02lld am\n",h,m%60,s);
}
return 0;
} I - 最少拦截系统
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65 Sample Output
2 题解思路:
就是求非递减子序列长度
#include<stdio.h>
#include<iostream>
using namespace std;
int n,a[30001],dp[30001],i,j;
int main()
{///最长不下降子序列的长度
while(cin>>n)
{
for(i=1; i<=n; i++)
cin>>a[i];
int ans=-0xffff;
for(i=1; i<=n; i++)
{///动规边界，a[i]之前的元素都比a[i]大，序列只有一个元素，长度为1
dp[i]=1;
for(j=1; j<i; j++)
{///状态转移方程
if(a[j]<=a[i])
///再一次WA，又是因为第一种情况一定一定要写dp[i]！！！
///由于是比较长度，所以第二种情况为a[i]加到前面的序列中去，使序列长度+1
dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}///找到最大那个不下降子序列
cout<<ans<<endl;
}
}
inline char gc()
{
static char buff[100000000],*S=buff,*T=buff;
return S==T&&(T=(S=buff)+fread(buff,1,100000000,stdin),S==T)?EOF:*S++;
} J - FatMouse's Speed
很多肥老鼠认为，长的越肥，奔跑速度就越快，为了反驳这个观点，你现在需要对老鼠的体重和速度进行研究，你要在老鼠序列中找出一个子序列，使得老鼠的体重在增加，但是速度却在减慢
Input
输入以eof结束。
输入中每行有两个正整数，分别表示老鼠的体重和速度，范围均在1到10000之间，输入数据最多有1000只老鼠。
某些老鼠可能有相同的体重，某些老鼠可能有相同的速度，某些老鼠可能体重和速度都相同。
Output
我们是要在原来的老鼠序列中，找到一个最长的子序列，使得这个子序列中老鼠的体重在严格增加，速度却在严格降低。
首先输出满足条件的最长的子序列的长度。
其次，输出一个最长子序列的方案，要求输出每个老鼠在输入时候的编号，每个编号占一行，任意一种正确的方法都会被判正确。
Sample Input
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
Sample Output
4
4
5
9
7
题解思路: 先按一个排序 (升序或者降序),再求另一个的最长 递减(递增)子序列的长度:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1005;
struct node{
int weight;
int speed;
int num;
};
node p[maxn];
int dp[maxn];
bool cmp(node A,node B){
if(A.weight != B.weight) return A.weight<B.weight;
else return A.speed>B.speed;
}
void solve(){
int k = 1,x,y;
while(scanf("%d%d",&x,&y)!=EOF){
p[k].weight = x;
p[k].speed = y;
p[k].num = k;
k++;
}
sort(p+1,p+k+1,cmp);
int ans = 0;
for(int i = k;i>=1; i--){
dp[i] = 1;
for(int j = i; j<=k; j++){
if(p[j].weight>p[i].weight&&p[j].speed<p[i].speed){
dp[i] = max(dp[i],dp[j]+1);
}
}
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
for(int i = 1; i<=k; i++){
if(dp[i] == ans){
printf("%d\n",p[i].num);
ans--;
}
if(ans == 0) break;
}
}
int main()
{
solve();
return 0;
}
K - Jury Compromise
没写出来~
L - Common Subsequence
最长公共子序列 水题
M - Help Jimmy
题解:https://blog.csdn.net/qq_43857314/article/details/99948935
N - Longest Ordered Subsequence
最长上升子序列长度 模板题
O - Treats for the Cows
区间DP 题解:https://blog.csdn.net/qq_43857314/article/details/99702166
P - FatMouse and Cheese
还没做 题解 一会儿更新
Q - Phalanx
求最多对称子矩阵:
题解:https://blog.csdn.net/qq_43857314/article/details/99718740
R - Milking Time
没写~
S - Making the Grade
A straight dirt road connects two fields on FJ's farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down).
You are given N integers A1, ... , AN (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ Ai ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B1, . ... , BN that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is
| A 1 - B 1| + | A 2 - B 2| + ... + | AN - BN |
Plea***pute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer elevation: Ai
Output
* Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation.
Sample Input
7
1
3
2
4
5
3
9
Sample Output
3 题目思路:用该序列里面的数替换该序列里面的数 使得最后的序列可以单调上升或递减,问最小的w是多少,w为 相邻差的绝对值之和
题解:
注意 ai很大 ,但是 n很小 所以用 离散化处理一下 即可:
dp[i][k]表示 把第i个数 换成 排序后的第k个数 产生的最小价值:
//#include<bits/stdc++.h>
#define ll long long
#pragma GCC optimize(2)
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=1e5+1000;
const int INF=1e9+7;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m,temp;
ll a[maxn],b[maxn];
ll dp[2005][2005];
ll AC()
{
for(int i=1;i<=n;i++)
{
ll pre=INF;
for(int k=1;k<=n;k++)
{
pre=min(pre,dp[i-1][k]);
dp[i][k]=fabs(b[k]-a[i])+pre;
}
}
ll re=INF;
for(int i=1;i<=n;i++)
re=min(dp[n][i],re);
return re;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
ll res=AC();
reverse(a+1,a+1+n);
res=min(res,AC());
printf("%lld\n",res);
return 0;
} 总结:
1.每一个状态都很重要,想清楚最优状态可分解为什么
2.一般可以根据n来判断dp的性质
3.可以通过记录上一层的最优来 实现加速状态转移
京公网安备 11010502036488号