美高梅6s投注盘:没有上司的舞会,卢斯的进位制

2823 锁妖塔

 时间限制: 1
s    空间限制: 128000
KB    题目等级 : 黄金
Gold

题目描述 Description

琐妖塔会在一会儿后倒塌。大量妖魔涌出塔去,塔内的楼梯都挤满了人(哦,错了,是妖),(那他们怎么不飞下去–)要求是,景天一行一定要下塔,琐妖塔一共N层,但是他突然大发慈悲,觉得妖怪是无辜,所以他不想踩死这些妖魔,所以他的速度最多比妖怪速度大K(否则会踩死妖怪的),并且速度不能比妖怪们慢,否则会被踩死。琐妖塔一共有N层,并且每层怪物逃跑的速度都不相同,景天每下一层,可以选择将他的速度加快一个单位或者减慢一个单位或者保持原来的速度不变。并且他下每一层的速度之和除以(N-1)要尽量大。当然跑下楼时他一定要活着。
现在景天刚拿到镇妖剑,头有点热,不能思考了,请你编个程序帮帮他吧!
提示:1楼不需要再下了,N层楼只需要下N-1层。并且在第N层楼到N-1层时必须为初始速度。

输入描述 Input
Description

第一行,三个整数N,V(初始速度),K(最多比其他妖快的速度值)
第二行,N-1个整数,分别代表从第二层到第N层的妖怪的速度
其中2〈=N〈=100,0〈=K〈=100,1〈=V〈=100。

输出描述 Output
Description

美高梅6s投注盘:没有上司的舞会,卢斯的进位制。若能下楼,输出速度之和除以(N-1),保留两位小数。
若不能,那就仰天大吼一声,输出“REN
JIU SHI BU NENG REN CI!”(不含引号)

样例输入 Sample
Input

Input1
3 3
2
2
2

美高梅6s投注盘:没有上司的舞会,卢斯的进位制。Input2
3 3
0
美高梅6s投注盘:没有上司的舞会,卢斯的进位制。2
2

样例输出 Sample
Output

美高梅6s投注盘:没有上司的舞会,卢斯的进位制。Output1
3.50
Output2
REN JIU
SHI BU NENG REN CI!

数据范围及提示 Data
Size & Hint

RT

 1 #include<cstdio>
 2 #include<queue>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef double db;
 6 int n,v,k;
 7 struct meico{
 8     int v;
 9     int ceng;
10     int tot;
11 };
12 db ans=0;
13 const int maxn=1000;
14 int spd[maxn],cg[]={0,1,0,-1},maxs[maxn];
15 bool flag;
16 void dfs(int vv,int ceng,int tot){
17     if(ceng==1){
18         flag=1;ans=max(ans,(db)((db)(tot)/db(n-1)));
19         return ;
20     }
21     if(flag) return;
22     for(int i=1;i<=3;i++){
23         int v1=vv+cg[i];
24         if(vv>=spd[ceng-1]&&(vv-spd[ceng-1])<=k){
25             if(ceng-1!=1)
26               dfs(v1,ceng-1,tot+v1);
27             else dfs(v1,ceng-1,tot);
28         }
29     }
30 }
31 int main()
32 {
33     scanf("%d%d%d",&n,&v,&k);
34     for(int i=1;i<n;i++)
35       scanf("%d",&spd[i]);
36     
37     if(v>=spd[n-1]&&v-spd[n-1]<=k){
38         dfs(v,n,v);
39         if(ans!=0)
40           printf("%.2lf\n",ans);
41         else printf("REN JIU SHI BU NENG REN CI!"); 
42     }
43     else{
44         printf("REN JIU SHI BU NENG REN CI!");
45         return 0;
46     }
47     
48     return 0;
49 }

刚开始一见这题,仙剑奇侠传!!!!!梦幻西游!!!!!!!鬼吹灯!!!!!!!!

由于题目下面写的宽搜,于是我一开始就打了宽搜….结果3^100直接MLE。 
美高梅6s投注盘:没有上司的舞会,卢斯的进位制。所以用深搜。 
这题我们枚举下楼的情况时,把速度+1放在最前面,这样能减掉不少枝,当搜到第一层的时候,更新答案,然后如果后面的最优答案小于当前最优答案,就减掉。

1380 没有上司的舞会

 

题目描述 Description

     
Ural大学有N个职员,编号为1~N。他们有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会,要求与会职员的快乐指数最大。但是,没有职员愿和直接上司一起与会。

输入描述 Input Description

第一行一个整数N。(1<=N<=6000)
接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。

输出描述 Output Description

输出最大的快乐指数。

样例输入 Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

各个测试点1s

树形DP,顾名思义就是在树上分阶段搞状态转移。这道题就是一个既典型又很简单的例子。
首先明确对于每个节点能够决定它对应的最优解的节点就是他的所有儿子节点。
然后,每个节点都有选,不选两种情况,对于这两种情况,需要对它进行分类讨论。
如果这个节点选,那么它的所有儿子节点一定都不选,dp[i][1]=Σ(dp[j][0])+r[i]

如果这个节点不选,他的儿子节点就可选可不选,dp[i][0]=Σmax(dp[j][1],dp[j][0])+r[i]

最终答案为max(dp[root][0],dp[root][1])

/*Cola说必须用邻接链表*/
#include<iostream>
#include<cstdio>
using namespace std; 
int n,r[6010],dp[6010][2],head[6010],num,fa[6010];
struct node{
    int to,pre;
}e[6010];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
void dfs(int k){
    for(int i=head[k];i;i=e[i].pre){
        int v=e[i].to;
        dfs(v);
        dp[k][0]+=max(dp[v][0],dp[v][1]);
        dp[k][1]+=dp[v][0];
    }
    dp[k][1]+=r[k];
}
int main(){
    freopen("manager.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&r[i]);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d%d",&y,&x);
        Insert(x,y);fa[y]=x;
    }int root;
    for(int i=1;i<=n;i++)if(fa[i]==0){root=i;break;}
    dfs(root);
    int result=max(dp[root][0],dp[root][1]);
    printf("%d",result);
}

 

时间限制: 1 s

 空间限制: 32000
KB

 题目等级 : 青铜
Bronze

题目描述 Description

著名科学家卢斯为了检查学生对进位制的理解,他给出了如下的一张加法表,表中的字母代表数字。 例如下图:                                                    

其含义为:

L+L=L,L+K=K,L+V=V,L+E=E

K+L=K,K+K=V,K+V=E,K+E=KL         ……

E+E=KV

+ L K V E
L L K V E
K K V E KL
V V E KL KK
E E KL KK KV

 

 

相关文章