上次说到的那个问题，是用暴力破解，但是我电脑跑到30位的时候就跑不动了，现在我想出一种新的算法，经过验证是对的，但是我无法证明这种算法的正确性，请数学大神帮我证明无比感谢，我再重新描述一下问题：
小明的导师给小明分配任务，每天都有不为0的任务量，如20,40,10,20，但是小明有心脏有问题，最多连续工作两天就必须休息一天，这让小明的导师很头疼，请问如果给定任务列表，小明怎么安排才能做最多的工作，求小明最多干多少活。
我的思路是这样的：每一天只有两种状态，一种是工作，一种是休息，我们就取到当天为止最大的工作量，所以要记录小明已经连续工作的天数，如果小明已经连续工作零天，那么当天必须工作才能获取的最大值，（我们把工作的顺序记录下来1表示工作，0表示休息，最终以便求和）；如果小明已经工作一天那么，就让小明今天也工作才能达到最大值；如果说小明已经连续工作了两天，那我们先把今天休息，然后算出最大工作量然后记录下来，然后如果今天选择工作的话，那么就必须昨天休息，或者是前天休息，才能让今天继续工作，所以分别把昨天休息，和前天休息的最大工作量算出来，然后比较这三种工作量，取最大的工作量，然后把对应最大工作量的顺序记录下来。然后再进行下一天的决策。
注意上面是我递推的思路，即（d代表工作天数，max代表当前最大工作量,work代表当天的工作量）
if d<=1
max=max work；
else
max=max{ 3中决策的最大工作量 }；
需要注意的是，每次要决策完后一定要把决策的工作序列记录下来，以便后面调用，如 1101等等，这个算法可以说是一种动态规划算法，也可以说是一种贪心算法，现在就是没有证明这种算法的正确性，请大神证明：我的实现如下(java)
public class Main3 { static class Node{ boolean[] all=null; int index=0; int days=0; public Node(int length){ all=new boolean[length]; } public int sum(int[] workList){ int sum=0; for(int i=0;i<index;i ){ if(all[i]){ sum =workList[i]; } } return sum; } public static Node max(Node a,Node b,int[] workList){ return a.sum(workList)>b.sum(workList)?a:b; } public static Node max(Node a,Node b,Node c,int[] workList){ Node temp=max(a,b,workList); return max(temp,c,workList); } public void copy(Node node){ for(int i=0;i<index;i ){ node.all[i]=all[i]; node.index=index; node.days=days; } } } public static int getMax(int[] workList){ if(workList.length<=2){ int sum=0; for(Integer temp:workList){ sum =temp; } return sum; }else{ Node pre=new Node(workList.length); pre.all[0]=true; pre.all[1]=true; pre.index=2; pre.days=2; Node now=null; for(int i=2;i<workList.length;i ){ if(pre.days==2){ //这一天休息创建一个Node Node a=new Node(workList.length); pre.copy(a); a.days=0; a.all[a.index]=false; a.index ; //这一天上班,但是让昨天不上班 Node b=new Node(workList.length); pre.copy(b); b.days=1; b.all[b.index]=true; b.all[b.index-1]=false; b.index ; //这一天上班,但是让前天天不上班 Node c=new Node(workList.length); pre.copy(c); c.all[c.index]=true; c.all[c.index-2]=false; c.index ; //选取最大值 now=Node.max(a, b, c, workList); }else{ //如果这已经工作天数不是2，那么今天工作肯定达到目前最大值 Node d=new Node(workList.length); pre.copy(d); d.days=pre.days 1; d.all[d.index]=true; d.index=pre.index 1; now=d; } pre=now; } return now.sum(workList); } } public static void main(String[] args) { int[] workList=new int[]{2000,10,2000,2000}; System.out.println(getMax(workList)); } }
