HDU 6778 car (group enumeration -- > shape pressure DP)

HDU 6778 Car ( Group enumeration –> Pressure dp)

notes ：

This article first analyzes tle I really want to dfs Ideas , Look at the transition dp

subject ：

wa spot ：

The title says 2 The license plates may be the same , But a car with the same license plate cannot be counted as 1 car , Is still 2 car .

Topic meaning conversion ：

Topic meaning conversion ：

Yes 10 A valuable item , Divide into 5 Group , Make this 5 The minimum and maximum values in the group , among 10 The value of an item can be 0, The number of each group can be 0.

analysis ：

< One > Full Permutation 1

Because the number of each group is uncertain , It is not easy to enumerate each group .

Blog portal , This blog uses group enumeration , First of all, the provisions of article i The number of items in the group will certainly be greater than the number of i-1 Group , So we can have A definite number of group assignments , Then select the specific device

void distrubit1_dfs(){}
...
void distrubit7_dfs(){}
void main()
{
	distrubit1_dfs();
	distrubit2_dfs();
	distrubit3_dfs();
	distrubit4_dfs();
	distrubit5_dfs();
	distrubit6_dfs();
	distrubit7_dfs();
}

< Two > Full Permutation 2

Enumerate this 10 Items ,10 There are... Items 5 A choice , $5^{10}$ In this case , And in this case, there is no way to reduce the expenses , Meeting t, It is written in the following way （ I use 10 A cycle has been tried , It will be tle）

void dfs(int car_id)
{
    if(car_id==10)
    {
        int now=day_sum[1];
        for(int day=1;day<=5;++day) now=min(now,day_sum[day]);
        ans=max(now,ans);
        return;
    }
    for(int day=1;day<=5;++day)
    {
        day_sum[day]+=car[car_id];
        dfs(car_id+1);    // Can't prune 
        day_sum[day]-=car[car_id];
    }
}

< 3、 ... and > state dp

What changes over time is the state , It means that the state of each moment is enumerable

Because only one item of each kind can be taken , Then the state is determined by whether the object is taken . And the change of time is day An increase in .

That is to say, the discussion listed above is the discussion of No 1,2,k Groups are objects , And change state dp The discussion is The first 1 To the first k Group time , Which objects have been assigned .

#include "iostream"
#include "algorithm"
#include "cstring"
#include "vector"
using namespace  std;
const int DAY=6;
const int NUM=1<<10+2;
int car[20];
int n,ans;
int dp[DAY][NUM];  // The first day Group   The transition quantity is .. The minimum amount of time 
void StatusDp()
{
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0x3f3f3f3f;
    for(int day=1;day<=5;++day)
        for(int last=0;last<(1<<10);++last)
        {
            if(dp[day-1][last]==-1)continue;
            for(int wantdo=0;wantdo<(1<<10);++wantdo)
            {
                if(last&wantdo)continue;
                int now=0;
                for(int k=0;k<10;++k)
                {
                    if( (wantdo>>k) &1)now+=car[k];
                }
                dp[day][last|wantdo]=max( dp[day][last|wantdo], min(dp[day-1][last],now ) );
            }
        }
}
int main()
{
//    freopen("in.text","r",stdin);
    int cas;
    scanf("%d",&cas);
    while (cas--) {
        memset(car, 0, sizeof(car));
        scanf("%d", &n);
        for(int tem,i=1;i<=n;++i)
        {
            scanf("%d",&tem);++car[tem%10];
        }
      StatusDp();
        cout<<n-dp[5][1023]<<endl;
    }
    return 0;
}