leetcode不知道多少题

冷不防 2022-09-14 09:25 65阅读 0赞

一堆程序，有互斥的，只要不互斥就可以同时运行，互斥的只能单独运行。求最短的运行时间，时间=可以一起运行程序中的最大时间+n个单独运行程序时间

思路

1.  01背包，搜就行了

#include<stdio.h>
    #include<string.h>
    int min(int a, int b){ 
        if(a<b)
            return a ;
        else return b;
    }
    int max(int a,int b){ 
        if(a>b)
            return a;
        else
            return b;
    }
    int canput(int *stark,int start,int *top,int **choice,int end){ 
        int j;
        for(j=0;j<*top;j++){ 
            if(*((int*)choice+end*stark[j]+start)==1)
                return 0;
        }
        return 1;
    
    }
    int time1(int *cast,int *stark,int end,int *top){ 
        int j ,i,r=0,maxcast=0;
        for(j=0;j<*top;j++){ 
            maxcast = max(cast[stark[j]],maxcast);//cast的标号写错
        }
        i=0;j=0;
        int flag[end];
        memset(flag,0,sizeof(int)*end);
        for(j=0;j<*top;j++){ 
            flag[stark[j]]=1;
        }
        for(j=0;j<end;j++){ //找不能一起运行的程序
            if(flag[j]==0){ 
                r = r+cast[j];
            }
        }
        r = r + maxcast;
        return r;//忘记return了·····
    }
    void tree8(int *stark,int start,int end,int *cast,int **choice,int *result,int *top){ 
        if(start==end){ 
            int r1 = time1(cast,stark,end,top);
            *result = min(r1,*result);
            return;
        }
        else {   //搜就完事了
            if(canput(stark,start,top,choice,end)){ 
                stark[(*top)++]=start;
                tree8(stark,start+1,end,cast,choice,result,top);
                (*top)--;
            }
            tree8(stark,start+1,end,cast,choice,result,top);
        }
    }
    
    void calautor(int n,int *cast,int **choice,int *result){ 
        int stark[n];
        memset(stark,-1,sizeof(int)*n);
        *result = 9999;
        int top =0;
        tree8(stark,0,n,cast,choice,result,&top);
    }
    
    int main(){ 
        int n = 4;
        int choice[4][4] = { { 0,0,0,0},{ 0,0,0,0},{ 0,0,0,1},{ 0,0,1,0}};
        int result = 0;
        int cast[4] = { 1,8,7,4};
        calautor(n,cast,(int**)choice,&result);
        printf("reslut = %d\n",result);
    }