HackerEarth-Faizu on a space war

H
Problem NameFaizu on a space war
JudgeHackerEarth
Problem Linkhttps://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/practice-problems/algorithm/faizu-on-a-space-war/
Algorithms & DSDynamic Programming , BitMasking
#include<bits/stdc++.h> using namespace std; typedef long long int ll; #define sf(n) scanf("%lld",&n); #define YES printf("YES\n"); #define NO printf("NO\n"); #define nl printf("\n"); #define PB push_back #define VST(V) sort(V.begin(),V.end()) #define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>()) #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll SET(ll NUM,ll POS) { return NUM | (1<<POS); } bool isOn(ll NUM,ll POS) { return (bool)(NUM & (1<<POS)); } ll n,mem[1<<16][17][17]; vector<ll>V; ll dp(ll mask,ll start,ll pre) { if(start!=-1&&mem[mask][start][pre]!=-1) { return mem[mask][start][pre]; } ll ans=0; for(ll i=0; i<n; i++) { if(isOn(mask,i)==0) { ll tm_mask=SET(mask,i); ll x=start; ll previous=V[i]; if(x==-1) { x=i; } else { previous=V[pre]; } ll val=(V[i]^previous)+dp(tm_mask,x,i); if(mask==(1<<n)-1) { val+=(V[x]+V[i]); } ans=max(ans,val); } } if(start!=-1)mem[mask][start][pre]=ans; return ans; } int main() { //freopen("1input.txt","r",stdin); fast; ll tcase=1; //cin>>tcase; for(ll test=1; test<=tcase; test++) { V.clear(); cin>>n; for(ll i=0; i<n; i++) { string s; cin>>s; ll siz=s.size(); ll sum=0; for(ll j=0; j<siz; j++) { sum+=s[j]-'a'+1; } V.PB(sum); } for(ll i=0; i<(1<<n)+10; i++) { for(ll j=0; j<=n; j++) { for(ll k=0; k<=n; k++) { mem[i][j][k]=-1; } } } ll ans=dp(0LL,-1,0); cout<<ans<<"\n"; } return 0; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!