Problem Description

This is a simple problem about string. Now a string S contains only ‘0’-‘9’. ?? wants to select a subsequence from this string. And makes this subsequence score maximum. The subsequence’s score is calculated as follows:
Score= Value – Total_Cost
The calculation of the Cost is as follows:
If the number of characters x in the subsequence is kx, And the two coefficients are ax,bx,The cost of character x calculated as follows:

The calculation of the Value is as follows:

Value=0;
for(int i=1;i<=length(substr);++i){
     for(int j=1;j<=length(substr);++j){
          if(i!=j)
              Value+=w[id[i]][id[j]];
     }
}

id[i] is the position of the subsequence’s ith character in the original string,for example,if the original string is “13579”,and the subsubquence is “159”,then the array id ={1,3,5}. The w is a weight matrix.

 

Input

The first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains one integers n, the length of a string.
Next line contains the string S.
Next ten lines,each line contains ai,bi,denote the char i’s(0-9) coefficients
Next is a n*n matrix w.
Limits:
T<=20,
0<=n<=100
0<=ai<=bi<=1000
0<=w[i][j]<=50

 

Output

Each test output one line “Case #x: y” , where x is the case number ,staring from 1. y is the Maximum score.

 

Sample Input

 

Sample Output

 

Author

FZU

 

Source

 

Recommend

wange2014

 

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 #include<queue>

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 inline int min(int a,int b){return a<b?a:b;}

 struct edge{

     int v,nxt,f;

 }e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v,int w){

     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=w;hd[u]=mct;return;

 }

 void insert(int u,int v,int w){

     add_edge(u,v,w);add_edge(v,u,);

     return;

 }

 int S,T;

 int d[mxn];

 queue<int>q;

 bool BFS(){

     memset(d,,sizeof d);

     q.push(S);d[S]=;

     while(!q.empty()){

         int u=q.front();q.pop();

         for(int i=hd[u];i;i=e[i].nxt){

             int v=e[i].v;

             if(!d[v] && e[i].f){

                 d[v]=d[u]+;

                 q.push(v);

             }

         }

     }

     return d[T];

 }

 int DFS(int u,int lim){

     if(u==T)return lim;

     int f=,tmp;

     for(int i=hd[u];i;i=e[i].nxt){

         int v=e[i].v;

         if(d[v]==d[u]+ && e[i].f && (tmp=DFS(v,min(lim,e[i].f)))){

             e[i].f-=tmp;

             e[i^].f+=tmp;

             lim-=tmp;

             f+=tmp;

             if(!lim)return f;

         }

     }

     d[u]=;

     return f;

 }

 int Dinic(){

     int res=;

     while(BFS()){res+=DFS(S,INF);}

     return res;

 }

 int n,m,ed,cnt;

 char s[];

 int mp[][];

 int a[],b[];

 void Build(){

     ed=n*(n-)/;cnt=;

     S=;T=ed+n++;

     int i,j;

     for(i=;i<=n;i++){

         for(j=i+;j<=n;j++){

             ++cnt;

             insert(S,cnt,mp[i][j]+mp[j][i]);

             insert(cnt,ed+i,INF);

             insert(cnt,ed+j,INF);

         }

     }

     for(i=;i<=n;i++){

         int c=s[i]-''+;

         insert(ed+i,T,a[c-]);

         insert(ed+i,ed+n+c,INF);

     }

     for(i=;i<=;i++){

         int u=ed+n+i+;

         insert(u,T,b[i]-a[i]);

     }

     return;

 }

 void init(){

     memset(hd,,sizeof hd);mct=;

     return;

 }

 int cas;

 int main(){

     int i,j,u,v;

     cas=read();int cct=;

     while(cas--){

         int ans=;

         init();

         n=read();

         scanf("%s",s+);

         for(i=;i<=;i++){a[i]=read();b[i]=read();}

         for(i=;i<=n;i++)

             for(j=;j<=n;j++)

                 mp[i][j]=read(),ans+=mp[i][j];

         Build();

         ans-=Dinic();

         printf("Case #%d: %d\n",++cct,ans);

     }

     return ;

 }