GYM101061F(Fairness-dfs||dp)

Fairness

题意：

• 老父亲给两个儿子分钱，在分钱的过程中尽可能的将钱的差值尽可能的小

思路1：

• 采用dfs将所有的分钱方式都列举出来，并在列举过程中进行比较（剪枝）。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int a[110];
int n,maix;
void dfs(int pos,int d,int s,int cnt)
{
   int count=abs(d-s);//计算当前这一次的差值
   if(cnt>=maix)//比较过程中最大值差值与最终的差值，假如比最终的差值都大，说明这一次分钱已经没有意义
   {
       return ;
   }
   if(pos>n)//当钱都分完了，最终的差值就是过程中的最大差值
   {
       maix=cnt;
       return ;
   }
   if(count>cnt)//当前差值与过程中的最大差值作比较
   {
       cnt=count;
   }
   pos++;
   dfs(pos,d+a[pos],s,cnt);
   dfs(pos,d,s+a[pos],cnt);
   return ;
}
int main( )
{
   int t;
   scanf("%d",&t);
  while(t--)
   {
       cin>>n;
       for(int i=1;i<=n;i++)
       {
           cin>>a[i];
       }
       maix=INF;
       dfs(1,a[1],0,0);
       cout<<maix<<endl;
   }
   return 0;
}

思路2：

• dp[i][j]表示前i枚硬币中两人所得硬币总面额差值为j时的的最小差值，那么对于第i枚硬币有两种情况，给第一个人和给第二个人，进而有两种转移：
  dp[i][j+a[i]]=min(dp[i][j+a[i]],max(dp[i-1][j],abs(j+a[i]))
  dp[i][j-a[i]]=min(dp[i][j-a[i]],max(dp[i-1][j],abs(j-a[i]))

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int dp[110][10010];
int a[110];
int n;
int main( )
{
   int t;
   cin>>t;
   while(t--)
   {
       cin>>n;
       for(int i=1;i<=n;i++)
       {
           cin>>a[i];
       }
       for(int i=0;i<=n;i++)
       {
           for(int j=0;j<=20000;j++)
           {
               dp[i][j]=INF;
           }
       }
       dp[0][10000]=0;
       for(int i=1;i<=n;i++)
       {
           for(int j=0;j<=20000;j++)
           {
               if(dp[i-1][j]!=INF)
               {
                   dp[i][j+a[i]]=min(dp[i][j+a[i]],max(dp[i-1][j],abs(j+a[i]-10000)));
                   dp[i][j-a[i]]=min(dp[i][j-a[i]],max(dp[i-1][j],abs(j-a[i]-10000)));

               }
               
           }
       }
       int ans=INF;
       for(int i=0;i<=20000;i++)
       {
           ans=min(dp[n][i],ans);
       }
       cout<<ans<<endl;
   }
   return 0;
}