HDOJ1074
import java.util.*;
/** * @author xiliang.zxl * @date 2015-05-08 14:04 */
public class Main {
/** number: oj1074 title : homework solution task: give a solution to minimize the cost of delay input: 2 3 Computer 3 3 English 20 1 Math 3 2 3 Computer 3 3 English 6 3 Math 6 3 output: 2 Computer Math English 3 Computer English Math solution time complex: 2^n solution brief introduction: use the math bit property : 1 -> 2^15 can imitate all middle station . whats more, this is can be a dp process. design a data structure and use dp theory. abstract model: N task , 2^N middle state , final state is all N task touched. description : all match upper model questions can use this solution template. */
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int cnt=scanner.nextInt();
while (cnt-->0){
List<Course> list=new ArrayList<Course>();
int courseCnt=scanner.nextInt();
while (courseCnt-->0){
Course course=new Course();
course.name=scanner.next();
course.deadline=scanner.nextInt();
course.needDays=scanner.nextInt();
list.add(course);
}
findSolution(list);
}
}
public static int[]parentAux=new int[32768];
public static int[]timeAux=new int[32768];
public static int[]delayAux=new int[32768];
public static void initAux(int size){
for(int i=0;i<=size;++i){
parentAux[i]=timeAux[i]=-1;
}
}
public static void findSolution(List<Course> courses){
initAux(courses.size());
int i=0,max= (int) Math.pow(2,courses.size())-1;
while(++i<=32768){
if(i>max) break;
Struct<Integer> struct=invokeDP(i,courses);
parentAux[i]=struct.parent;
timeAux[i]=struct.time;
delayAux[i]=struct.delay;
}
List<Integer> orderList=getHomeWorkOrder(max);
System.out.println(delayAux[max]);
for(Integer workIndex:orderList){
System.out.println(courses.get(workIndex).name);
}
}
public static List<Integer> getHomeWorkOrder(int max){
List<Integer> orderList=new ArrayList<Integer>();
while(max!=-1){
int positon=max;
if(parentAux[max]!=-1)
positon=max-parentAux[max];
orderList.add(0,parsePosition(positon,0));
max=parentAux[max];
}
return orderList;
}
public static int parsePosition(int position,int offset){
for(int i=offset;i<=15;++i){
if(((1<<i)&position)!=0)
return i;
}
return -1;
}
public static Struct invokeDP(int i, List<Course> courses){
//
Struct struct=new Struct(0,0,-1);
if((i&(i-1))==0){
struct.time=courses.get(parsePosition(i,0)).needDays;
int delay=courses.get(parsePosition(i,0)).needDays-courses.get(parsePosition(i,0)).deadline;
if(delay>0){
struct.delay=delay;
}
return struct;
}
int position=parsePosition(i,0),bestPosition=position,minDelay=Integer.MAX_VALUE;
while (position!=-1){
int time=timeAux[i-(1<<position)],cost=delayAux[i-(1<<position)];
int delay=courses.get(position).needDays+time-courses.get(position).deadline;
if(delay>0){
cost+=delay;
}
if(cost<minDelay || (cost==minDelay &&
courses.get(position).name.compareTo(courses.get(bestPosition).name)>0)){
bestPosition=position;
minDelay=cost;
}
position=parsePosition(i,position+1);
}
struct.time=timeAux[i-(1<<bestPosition)]+courses.get(bestPosition).needDays;
struct.parent=i-(1<<bestPosition);
struct.delay=minDelay;
return struct;
}
public static class Course{
String name;
int deadline;
int needDays;
}
public static class Struct<T>{
T time;
T delay;
T parent;
public Struct(T time, T delay, T parent) {
this.time = time;
this.delay = delay;
this.parent = parent;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.