Codeforces Round墯127(Div.1)D.Brand New Problem暴力dp

D.Brand New Problem
テーマ接続:
http://www.codeforces.com/contest/201/problem/D
Description
A Widely known among some people Belarusian sport programmer Lesha decided to make some moneney to buy a a one square meterlar fat.To do this、he wants to make and carry out Super Super Rated Matttttttttttthethethethethethe proproproproproproproproproproproproproproproproconconconconconconmmmsasasasasasasasasasasasasasasasasasasatotototototototototototorerererererereaaaaaaaaaaaaaaaaaaaaaaaaa' s problem、caling each of them an offsensive word「duped」.And one day they nearly quareled over yet another proble Ivan wouldn't accept.
You are invited to act as a fair judge and determine whethe proble is indeed brand new、or Ivan is right and the problem some blement to those used in the previous SRMs.
Youber given the description s of Lesha's problem and each of Torcorder.com archive probles.The description of each problem is a sequence of words.Besides，it is Garanted that Lesha's problem hasのreptatwords。
The「simillarity」between Leshe's problem and some archive problem can be found as follows.Among all permuttions of wors in Leshe's problem we chose the one thatcurs in the archive proble problem as.ore.absetic.Iltence。we chose the one with the smalest number of inversions.The n the「simillarity」of a problem can be written a s，where n is the number of words in Leshe's and x the number of inversions the the the the mutite.Nortator。
The problem is cared brand new if there is not a single problem in Ivan's archive which contains a permutation of worsfrom Lesha's problem as.
Help the boys and determine whethe proposed problem is new、or specify the problem from the archive which reems Leshe's problem the most、the herswise.
Input
The first line contains a single integer n(1̵≦?n̵≦?15)-the number of wors in Leshe's proble.The second line contains n space-separated worss-the shart proption.
The third line contains a single integer m(1?≦?mm?≦≦?10)-the number of problems the Toroder. com archive.Next m lins contain the descriptions of the proms the proass"s"s.shehers the ssshere"s 1.sshere...s.sshere...s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.s.thethethetheproblem and si is a word of the problem description.
All words from all problem descriptions contain no more than 10 lowercase English letters.It is garanted that the total length of words in proble descriptions does not exced 500015.
Output
If Lesha's problem is brand new、print string「Brand new proble！」without
Otherwise，on the first line prest the index of the archive problem Leshe's problem most.If there re re multile such problems，print the one with the smalest index.On the second line indent.ortions。where p is the「simillarity」between this proble m and Lesha's one.The archive problems are numbered starting from one in the order in the which the input.
Sample Input
4 find the next palindrome 1 10 find the previous palindrome or print better luck next time
Sample Output
1[:???:]
ベント
題意
今あなたにn個の単語をあげます。n個の単語は全部違っています。n<=15、単語の長さ<=10
そしてq回の問い合わせがあります
あなたにm個の単語を問い合わせるたびに、このm個の単語は前にあげたn個の一つかもしれません。そうではないかもしれません。そして、n個の単語の配列を探す必要があります。
次にq回問い合わせの後、n*(n-1)/2-最小の問い合わせの答え+1を出力します。
出力は特別です。答えはいくつですか？縦線をいくつ出力しますか？
配列が見つからなければ、Brand new probleを出力します。
クイズ:
第一の考え、暴力列挙が並ぶ様子、15！O（n），明らかにtle
それから私たちはどうすればいいですか？私たちは2^15*O（n）ができます。
dp[i]はiの状態で最小の逆順対数を表し、転移は明らかである。dp[i|（1<i|（1<そのまま走ればいいです。もちろんTLEもあります。
もっとも走る一番早いコードはこのようにしています。彼は謎の剪定を加えました。
この数の前の状態が更新されていないなら、そのままcontinueで走ります。
剪定の悟りがないとどうなりますか？大丈夫です。dpもあります。
dp[i][j]は、i状態を考慮した現在の逆数jの最小位置を表しています。
移行も簡単です。dp[i|(もちろん時間の複雑さは15^2*2^15*15で、謎の飛行です。
走るコード

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<15+5;
const int inf = 1e9;
char s[16][11],t[11];
int dp[maxn];
int ans1=0,ans2=inf;
int vis[20];
int n;
int ones[maxn];
int fi(char m[])
{
    for(int i=0;i<n;i++)
        if(strcmp(s[i],m)==0)
            return i;
    return n;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<1<<n;i++)
        ones[i]=ones[i>>1]+(i&1);
    for(int i=0;i<n;i++)
        scanf("%s",s[i]);
    int m;
    scanf("%d",&m);
    for(int id=1;id<=m;id++)
    {
        int num;scanf("%d",&num);
        for(int i=0;i<(1<<n);i++)
            dp[i]=inf;
        memset(vis,0,sizeof(vis));
        dp[0]=0;
        int pre = 0;
        while(num--)
        {
            scanf("%s",t);
            int p = fi(t);
            if(p==n)continue;
            if(pre&(1<<p))continue;
            //               ，   continue，       ……
            //    ，       ……
            pre=(pre&((1<<p)-1))|(1<<p);
            for(int i=(1<<n)-1;i>=0;i--)
                if(dp[i]<inf&&(i&(1<<p))==0)
                    dp[i|(1<<p)]=min(dp[i|(1<<p)],dp[i]+ones[i & ~((1 << p) - 1)]);
        }
        if(ans2>dp[(1<<n)-1])
        {
            ans1=id;
            ans2=dp[(1<<n)-1];
        }
    }
    if(ans1==0)printf("Brand new problem!
");
    else{
        printf("%d
",ans1);
        printf("[:");
        for(int i=0;i<n*(n-1)/2-ans2+1;i++)
            printf("|");
        printf(":]
");
    }
}

鶏肉の辛味

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<15+5;
const int maxn2 = 15*(15-1)/2+1;
const int inf = 1e9;
char s[16][11],t[11];
int dp[1 << 15][15 * (15 - 1) / 2 + 1];
int nxt[500016][16];
int ans1=0,ans2=inf;
int vis[20];
int n;
int ones[maxn];
int fi(char m[])
{
    for(int i=0;i<n;i++)
        if(strcmp(s[i],m)==0)
            return i;
    return n;
}
int solve()
{
    int num;scanf("%d",&num);
    fill(dp[0], dp[1 << n], inf);
    memset(nxt,-1,sizeof(nxt));
    int cnt = 0;
    for(int i=0;i<num;i++)
    {
        scanf("%s",t);
        int p = fi(t);
        if(p==n)continue;
        nxt[cnt][p]=cnt;
        cnt++;
    }
    for(int i=cnt-2;i>=0;i--)
        for(int j=0;j<n;j++)
            if(nxt[i][j]==-1)
                nxt[i][j]=nxt[i+1][j];

    dp[0][0]=0;
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<=n*(n-1)/2;j++)
        {
            if(dp[i][j]==inf)continue;
            for(int k=0;k<n;k++)
            {
                if((1<<k)&i)continue;
                if(nxt[dp[i][j]][k]==-1)continue;
                dp[i|(1<<k)][j+ones[i>>k]]=min(dp[i|(1<<k)][j+ones[i>>k]],nxt[dp[i][j]][k]);
            }
        }
    }
    for(int i=0;i<=n*(n-1)/2;i++)
        if(dp[(1<<n)-1][i]!=inf)
            return i;
    return inf;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<1<<n;i++)
        ones[i]=ones[i>>1]+(i&1);
    for(int i=0;i<n;i++)
        scanf("%s",s[i]);
    int m;
    scanf("%d",&m);
    for(int id=1;id<=m;id++)
    {
        int tmp = solve();
        if(ans2>tmp)
        {
            ans1=id;
            ans2=tmp;
        }
    }
    if(ans1==0)printf("Brand new problem!
");
    else{
        printf("%d
",ans1);
        printf("[:");
        for(int i=0;i<n*(n-1)/2-ans2+1;i++)
            printf("|");
        printf(":]
");
    }
}