제출 #219691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219691		MohamedAhmed04	Vještica (COCI16_vjestica)	C++14	0 / 160	79 ms	1656 KiB

vjestica

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 17 ;

string arr[MAX] ;
int freq[MAX][27] , dp[(1 << MAX)] ;
bool pref[MAX][MAX] ;
int n ;

bool cmp(string &a , string &b)
{
	return a.size() < b.size() ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
	{
		cin>>arr[i] ;
		for(auto &c : arr[i])
			freq[i][c-'a']++ ;
	}
	sort(arr , arr + n , cmp) ;
	for(int i = 0 ; i < n ; ++i)
	{
		dp[1 << i] = arr[i].size() ;
		for(int j = i+1 ; j < n ; ++j)
		{
			pref[i][j] = 1 ;
			for(int k = 0 ; k < 26 ; ++k)
			{
				if(freq[i][k] > freq[j][k])
					pref[i][j] = 0 ;
			}
		}
	}
	for(int mask = 1 ; mask < (1 << n) ; ++mask)
	{
		if(__builtin_popcount(mask) == 1)
			continue ;
		dp[mask] = 1e9 ;
		int prv = -1 , Max = 0 ;
		bool can = 1 ;
		for(int i = 0 ; i < n ; ++i)
		{
			if((mask & (1 << i)))
			{
				if(prv != -1 && !pref[prv][i])
					can = 0 ;
				prv = i ;
				Max = arr[i].size() ;
			}
		}
		if(can)
		{
			dp[mask] = Max ;
			continue ;
		}
		for(int sub = mask ; sub ; sub = (sub-1) & mask)
			dp[mask] = min(dp[mask] , dp[sub] + dp[mask ^ sub]) ;
	}
	return cout<<dp[(1 << n) - 1]+1<<"\n" , 0 ;
}		

• Subtask 1: 0 / 160