学习总结2.14

深搜将题目分配，如果是两个题目，就可以出现左左，左右，右左，右右四种时间分配，再在其中找最小值，即是两脑共同处理的最小值

#include <stdio.h>
int s[4];
int sum=0;
int brain[25][25];
int min=999;
int left=0,right=0;
void dfs(int x,int y){if(y>s[x]){//如果当前这套题目已经被复习完if(max(left,right)<min) min=max(left,right);//更新最小值return;}else{left+=brain[x][y];//左脑处理dfs(x,y+1);//递归left-=brain[x][y];//回溯right+=brain[x][y];//右脑处理dfs(x,y+1);//递归right-=brain[x][y];//回溯}
}
int max(int a,int b){return (a>b)?a:b;
}
int main()
{for(int i=1;i<=4;i++){scanf("%d",&s[i]);}for(int i=1;i<=4;i++){left=0,right=0;min=999;//初始化for(int j=1;j<=s[i];j++){scanf("%d",&brain[i][j]);}dfs(i,1);sum+=min;}printf("%d\n",sum);return 0;
}

比较简单的dp01背包

#include <stdio.h>
int dp[205][205]={0};
int n,m,t;
int a[205],b[205];
int max(int a,int b){return (a>b)?a:b;
}
int main()
{scanf("%d %d %d",&n,&m,&t);for(int i=1;i<=n;i++){scanf("%d %d",&a[i],&b[i]);}for(int i=1;i<=n;i++){for(int j=m;j>=a[i];j--){for(int k=t;k>=b[i];k--){dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+1);}}}printf("%d\n",dp[m][t]);return 0;
}