洛谷P2393 kkksc03临时抱佛脚动态规划,c++Sakuracode的博客-

【贪心+01背包】洛谷P2393kkksc03临时抱佛脚

NOIOL第三场pj竟然混了240分进了前25%，蒟蒻深感自己DP的薄弱（T3竟然连50分都拿不到），开始在洛谷刷DP，做背包的时候看到的这道题。没想到一道橙题卡了半天

传送门

分析

  题目说了要先做完一个题目集再做后面的，所以只要分别求四个子集的最优解，把它们相加就可以了。
  对于一个子集的最优解，我们就是把总时间分配到左脑和右脑，然后让两者较大的值尽可能小，即让他们尽可能接近。
  这里运用了贪心的思想，我们做完一个子集的题目，花费的时间是左脑和右脑花费时间大的那个，比如说左脑3，右脑5，我花费的时间就是5，那么让大的那个尽可能小也就是平均分就是最优解。
  如果你做过一道小s的游戏机电池这道贪心，你会发现到这里好像和那道题思路差不多（要是没看过就忽略掉），但是注意，这道题里开始做一道题目，直到做完，我们才能让这一半大脑去做下一道题，这是和那道电池题目的不同之处，这道题可能我们无法刚好分配出一半的时间给左脑，一半的时间给右脑，因为一道题目不能分割。举个例子，如果3道题分别要花费1、2、5的时间，我无论如何也不能分配出4这个时间吧，但是我可以让一半的大脑在不超过4的情况下，尽可能的大（让1、3在左脑）。这样，左脑和右脑花费时间较多的那个就是所需的最少时间（其实理解了就不难明白，认真看几遍就明白了）。
  经过上面的转换，我们发现求左半边大脑所需的时间就是在总时间不超过sum/2的情况下，选取若干道题目，让时间尽可能的大。 （这就是道0/1背包的裸题）求出左半边，右半边用sum减去左半边就得出了，最后求左半边和右半边的最大值，就是这个子集所花费的时间。
  最后不要忘了有4个子集，都要算出来啊

  最后蒟蒻贴上AC代码（话说这题是蒟蒻在luogu的第100道AC欸）：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int s1,s2,s3,s4,minn,sum; int t[25],f[25][620]; void dp(int n,int maxn){ memset(f,0,sizeof f); //在不超过maxn的情况下让价值尽可能大  for(int i=1;i<=n;i++){ for(int j=0;j<=maxn;j++){ if(t[i]>j)f[i][j]=f[i-1][j]; else f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+t[i]); } }  minn += (sum-f[n][maxn]);  sum = 0; } int main(){  ios::sync_with_stdio(false);  cin>>s1>>s2>>s3>>s4; for(int i=1;i<=s1;i++){   cin>>t[i];   sum+=t[i]; } dp(s1,sum/2); for(int i=1;i<=s2;i++){   cin>>t[i];   sum+=t[i]; } dp(s2,sum/2); for(int i=1;i<=s3;i++){   cin>>t[i];   sum+=t[i]; } dp(s3,sum/2); for(int i=1;i<=s4;i++){   cin>>t[i];   sum+=t[i]; } dp(s4,sum/2);  cout<<minn<<endl; return 0; } 

今天的文就到这里了（话说上篇差分的都没人看啊，不会是我写的太差了吧）