ZOJ 3541

题目大意:有n个按钮,第i个按钮在按下ti 时间后回自动弹起,每个开关的位置是di,问什么策略按开关可以使所有的开关同时处于按下状态


Description


There is one last gate between the hero and the dragon. But opening the gate isn't an easy task.

There were n buttons list in a straight line in front of the gate and each with an integer on it. Like other puzzles the hero had solved before, if all buttons had been pressed down in any moment, the gate would open. So, in order to solve the puzzle, the hero must press all the button one by one.

After some trials, the hero found that those buttons he had pressed down would pop up after a while before he could press all the buttons down. He soon realized that the integer on the button is the time when the button would automatic pop up after pressing it, in units of second. And he measured the distance between every button and the first button, in units of maximum distance the hero could reach per second. Even with this information, the hero could not figure out in what order he should press the buttons. So you talent programmers, are assigned to help him solve the puzzle.

To make the puzzle easier, assuming that the hero always took integral seconds to go from one button to another button and he took no time turnning around or pressing a button down. And the hero could begin from any button.

Input


The input file would contain multiple cases. Each case contains three lines. Process to the end of file.

The first line contains a single integer n(1 ≤ n ≤200), the number of buttons.

The second line contains n integers T1, T2, ..., Tn, where Ti(1 ≤ Ti ≤ 1,000,000) is the time the ith button would automatic pop up after pressing it, in units of second.

The third line contains n integers D1, D2, ..., Dn, where Di(1 ≤ Di ≤ 1,000,000) is the time hero needed to go between the ith button and the first button, in units of second. The sequence will be in ascending order and the first element is always 0.

Output


Output a single line containing n integers which is the sequence of button to press by the hero. If there are multiply sequences, anyone will do. If there is no way for the hero to solve the puzzle, just output "Mission Impossible"(without quote) in a single line.

Sample Input


2
4 3
0 3
2
3 3
0 3
4
5 200 1 2
0 1 2 3

Sample Output


1 2
Mission Impossible
1 2 4 3

Hint


In the second sample, no matter which button the hero pressed first, the button would always pop up before he press the other button. So there is no way to make all the button pressed down.

Solution


本题很容易想到区间DP,对于一个区间,一定是从某个端点开始,因为如果从中间开始之后按别的开关时一定会经过这个点。

状态

\(f_{i,j,0/1}\)

表示区间[i,j]从左/右端点开始的最小时间。

状态转移方程见代码。

//Writer : Hsz %WJMZBMR%tourist%hzwer
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <cstdlib>
#include <algorithm>
const int inf=0x3fffffff;
#define LL long long
using namespace std;
const int N=222;
int n;
LL t[N],d[N],f[N][N][2];
bool way[N][N][2];
int main() {
while(scanf("%d",&n)!=EOF) {
memset(f,0,sizeof f);
for(int i=1; i<=n; i++)
scanf("%lld",&t[i]);
for(int i=1; i<=n; i++)
scanf("%lld",&d[i]);
for(int l=2; l<=n; l++) {
for(int i=1; i+l-1<=n; i++) {
int j=i+l-1; if(f[i+1][j][0]+d[i+1]-d[i]<f[i+1][j][1]+d[j]-d[i])
f[i][j][0]=f[i+1][j][0]+d[i+1]-d[i],way[i][j][0]=0; else f[i][j][0]=f[i+1][j][1]+d[j]-d[i],way[i][j][0]=1; if(t[i]<=f[i][j][0]||f[i][j][0]>=inf)
f[i][j][0]=inf; if(f[i][j-1][1]+d[j]-d[j-1]<=f[i][j-1][0]+d[j]-d[i])
f[i][j][1]=f[i][j-1][1]+d[j]-d[j-1],way[i][j][1]=1; else f[i][j][1]=f[i][j-1][0]+d[j]-d[i],way[i][j][1]=0; if(t[j]<=f[i][j][1]||f[i][j][1]>=inf)
f[i][j][1]=inf;
}
}
int l,r,v;
if(f[1][n][0]<inf) {
printf("1");
l=2,r=n,v=way[1][n][0];
} else if(f[1][n][1]<inf) {
printf("%d",n);
l=1,r=n-1,v=way[1][n][1];
} else {
puts("Mission Impossible");
continue;
}
while(l<=r) {
if(!v) printf(" %d",l),v=way[l][r][0],l++;
else printf(" %d",r),v=way[l][r][1],r--;
}
printf("\n");
}
return 0;
}

最新文章

  1. 随笔分类 - [C#6] 新增特性
  2. SQL Server代理(7/12):作业活动监视器
  3. Linux vim编辑命令
  4. R之批处理
  5. SQL SERVER 2000 &amp; SQL SERVER 2005 数据缓存依赖
  6. JS中break continue和return的用法?
  7. 手动配置S2SH三大框架报错(一)
  8. 从概念到业务来看 To B 和 To C 产品区别在哪?
  9. Django笔记--模型
  10. 【CF1151F】Sonya and Informatics(动态规划,矩阵快速幂)
  11. Java多线程(五)线程的生命周期
  12. MT【265】a+b,ab
  13. Spark的Streaming + Flume进行数据采集(flume主动推送或者Spark Stream主动拉取)
  14. [转载] HTTP 协议中 URI 和 URL 的区别
  15. Java对象与JSON互相转换jsonlib以及手动创建JSON对象与数组——(二)
  16. oracle定时任务的编写及查看删除
  17. SSM实战——秒杀系统前言
  18. 【LeetCode】Path Sum II 二叉树递归
  19. 用mapreduce来操作hbase的优化
  20. ios7 - Custom UItabbar has a gap in the bottom

热门文章

  1. POJ 3076
  2. OpenCV打开摄像头失败
  3. 第6章 Spring MVC的数据转换、格式化和数据校验
  4. Tomcat安全设置与优化详解(非原创)
  5. Hashmap 详解和迭代器问题
  6. cloudfoundry service broker 制作
  7. F - Dima and Lisa(哥德巴赫猜想)
  8. C++程序开发的基本过程
  9. hiho一下 第174周
  10. Fiddler-AutoResponder 修改接口数据