简要题意及解析
1001
(N)个数分为(K+8)组，每组三个，记为((a,b,c))，方便起见要求(a leq b leq c)，每组的代价是((a-b)^2)，总代价为每组的代价之和。求最小的总代价。
将所有物品(a[i])从小到大排序，从后向前递推。(f[i][j])表示在第(i)个到第(N)个数中选(j)组的最小代价。
[f[i][j]=min_{N-i+1 leq 3 imes j} {f[i+2][j-1]+(a[i+1]-a[i])^2}
]
时间复杂度(O(Tnk))
(T)为数据组数，(n)为物品个数，(k)为所需组数。
1002
给出三个字符串(A,B,C)，问从(A)和(B)中按照与原顺序抽取一些字符，能不能组成(C)。
(f[i][j])表示从(A)的前(i)个和(B)的前(j)个中随意抽取，最多能组成(C)的前几位。
[f[i][j]=max{f[i-1][j]+1(if~~A[i]==C[f[i-1][j]+1]),f[i][j-1]+1(if~~B[j]==C[f[i][j-1]+1])}
]
时间复杂度(O(Tnm))
(T)是数据组数，(n,m)分别为(A,B)的长度。
1003
给出两个字符串(A)和(B)，求最短的字符串(C)，使得(A,B)都为(C)的子串
显然，(C)的长度(LenC=LenA+LenB-LCS(A,B))
其中(LCS)为最长公共子序列。
(f[i][j])表示(A)的前(i)个和(B)的前(j)个的(LCS)。
[f[i][j]=max{f[i-1][j],f[i][j-1],f[i-1][j-1]+1(if~~A[i]==B[j])}
]
在求(LCS)的过程中记录每个状态(f[i][j])是从哪里转移得来的，输出方案时，如果是从(f[i-1][j])，输出(A[i])，如果是从(f[i][j-1])，输出(B[j])，如果是从(f[i-1][j-1])，输出任一。
时间复杂度(O(Tnm))
(T)是数据组数，(n,m)是(A,B)的长度。
1004
给出一个(n)列的柱状图，每列宽度为(1)，求这个柱状图的最大子矩阵面积。
正常的二维动态规划状态不可行。注意到这个最大子矩阵的高度一定是给定的(n)列高度中的一个。可以考虑枚举每列作为这个子矩阵的高度，最长向左向右延伸长度。
如何向左向右延伸，二分不好做，可以倍增。
考虑向右延伸。(f[i][j])表示从第(i)个到第(i+2^j-1)个这个区间的最低高度。延伸时，可以从大到小枚举(j)，只要这个最低高度(geq)(h[i])，就可以向右走(2^j)步。
这个数组可以预处理求得。
[f[i][j]=min{f[i][j-1],f[i+2^{j-1}][j-1]}
]
时间复杂度(O(Tnlogn))
(T)为数据组数，(n)为列数。
有另一种方法，单调栈可以做到单组(O(n))
1005
给一个(n)行(m)列的(0/1)矩阵，求只由(1)构成的子矩阵面积最大值。
悬线法
枚举矩形的底边，再枚举每一列，考虑以这一列的高度(向上连续(1)的最长长度)作为矩形高度。和上题类似，还是保证这个高度向左向右尽量延伸。延伸可以用类似单调栈的方法，也可以和上题一样倍增(复杂度多一个(logm)，不过应该也能过)。
时间复杂度(O(Tnm))
(T)为数据组数，(n)为行数，(m)为列数。
1006
给出一个(n imes n)的黑白方阵，求白色矩形的数量。
枚举矩形的上下边界，求这种矩形的数量可以不重不漏。
这样问题就转化为了一维：确定上下边界(i)和(j)之后，如果(a[i][k])到(a[j][k])这一列均为白色，(p[k])为(1)，否则(p[k])为(0)。求连续(1)的块的种类数。
统计(p)中连续(1)的长度(L)，贡献为(L imes (L+1) div2)
时间复杂度(O(Tn^3))
(T)为数据组数，(n)方阵边长。
1007
给出一个长度为(n)的字符串(s)，你每次操作可以在(s)中插入一个字符，求最少几次能把(s)变成回文串。
巨坑 此题为多组数据，题目没说。
区间动态规划
(f[i][j])表示把([i,j])区间变为回文串最少次数。
[f[i][j]=min{f[i][j-1]+1,f[i+1][j]+1,f[i+1][j-1] (if~~s[i]==s[j])}
]
内存紧张，需要滚动数组。
时间复杂度(O(Tn^2))
(T)为数据组数，(n)为字符串长度。
1008
有一个宽度为(4)，深度为(n)的矿区，每个格子中有(1)到(20)的整数，表示一种矿物。可以从每个地表向下挖，可以在任何时候换到另一列，每到一个格子就把这个矿物装入(basket)，当(basket)中有相同种类的矿物时，这种矿物被取出到(pocket)，当(basket)中的矿物为(5)个不同矿物时，游戏结束。求(pocket)中最多有多少对矿物。
(f[i][j][k][l])表示（第一列挖到深度为(i)，第二列挖到深度为(j)，第三列挖到深度为(k)，第四列挖到深度为(j)）是否可行。每列挖到的位置定为((i,j,k,l))时，(basket)和(pocket)的状态是固定的，可以预处理求。
[f[i][j][k][l]=f[i-1][j][k][l]~~|~~f[i][j-1][k][l]~~|~~f[i][j][k-1][l]~~|~~f[i][j][k][l-1]
]
在每个可行的状态求最大值。
时间复杂度(O(Tn^4))
(T)为数据组数，(n)为矿区深度。
感谢(snophy)提供标程和题解
1009
给出两个字符串(A,B)，你可以对(A)做三种操作：((1))插入一个任意字符，((2))删除某个位置的字符，((3))把某个位置的字符替换成任意字符。最少几次能把(A,B)变为相同并输出方案。
(f[i][j])表示使用了(A)的前(i)个和(B)的前(j)个，使得两个串暂时相同的方案数。
[f[i][j]=min{f[i][j-1]+1,f[i+1][j]+1,f[i+1][j-1]+(A[i]==B[j])}
]
其中第一个转移为插入，第二个为删除，第三个为插入（如果相同不用操作）。
这题的输出方案非常麻烦，不仅需要记录从哪里转移，还要记录之前有几次删除(/)插入，因为操作的位置会被影响。
时间复杂度(O(Tnm))
(T)为数据组数，(n)为(A)长度，(m)为(B)的长度。
1010
(26)个字母分别对应一种编码，给出使用该种编码的一个密码串，再给出(N)个字符串，求用这(N)个字符串组成这个密码有多少种方案。
(f[i])表示组成密码的前(i)位的方案数。
状态转移很显然：
[f[i]=sum_{j=1}^{j leq N} f[i-L[j]]~~(if~~match(substr(i-L[j]+1,i),S[j]))
]
(S[j])为第(j)个字符串，(L[j])为(S[j])的长度。如果匹配，即可从(f[i-L[j]])转移到(f[i])，匹配可以用字符串(Hash)。
时间复杂度(O(TNL))
(T)为数据组数，(N)为字符串个数，(L)为密码串长度。
不过话说这题这样做复杂度是不对的。可以使用(AC)自动机求出匹配位置进行转移，这样复杂度更优，不过空间不够用，代码也附在后面了。
1011
求任意子串中(0)和(1)的数量差不超过(K)的长度为(N)的(0/1)串的个数。
很奇怪的状态但是它竟然是对的。(f[i][j][k])表示长度为(i )的(0/1)串，其中以第(i)个元素结尾的子串中，(0)的个数(-)(1)的个数(~~)最大值为(j)，(1)的个数(-)(0)的个数(~~)最大值为(k)的方案数。
[f[i][j]=f[i-1][j-1][k+1] (if~~jgeq 0) +f[i-1][j+1][k-1] (if~~kgeq 0)+f[i-1][j-1][k](if~~k==0)+f[i-1][j][k-1](if~~j==0)
]
时间复杂度(O(TNK^2))
(T)为数据组数，(N,K)同题意。
1012
给你一个(m imes n)的整数矩阵，在上面找一个(x imes y)的子矩阵，使子矩阵中所有元素的和最大。
预处理(S[a][b]=sum_{i=1}^{ileq a}m[i][b])
然后枚举矩阵上下边界。这个问题就转化为一维最大子段和。
时间复杂度(O(Tmn^2))或者(O(Tnm^2))
(T)为数据组数，(n,m)为矩阵长和宽。
1013
给出(n)种物品的价值和个数。把这些物品分为两组，求这两组价值和的最小差值。
多重背包可行性
(f[i])表示从这些物品中取得(i)的价值是否可能。
[f[i]=true(if~~exist f[i-j*v[k]]==true AndAnd jleq p[k])
]
(k)为物品编号，(j)为所取个数。
时间复杂度(O(TnSV))
(T)为数据组数，(n)为物品种数，(S)为物品个数和，(V)为物品总体积。
不过这个做法的复杂度依然不对，可以二进制分组或者(bitset)优化
1014
你的钱有(n)块，(m)个学校可以申请，申请第(i)这个学校你需要花费(a[i])，有(b[i])的概率成功，求最大的可能性。
类似(0/1)背包，条件概率公式。
(f[i])表示花费(i)能得到的最大概率。
[f[i]=max_{j=1}^{jleq m}{f[i-a[j]]+(1-f[i-a[j]] imes b[j])}
]
时间复杂度(O(Tnm))
(T)为数据组数，(n,m)如题意。
1015
(n)种物品每种一个，重量为(w[i])，价值为(p[i])。填满(F-E)的背包最少用多少价值。
(0/1)背包
(f[i])表示重量为(i)的背包最少装多少价值。
[f[i]=min_{j=1}^{jleq n}{f[i-w[j]]+p[j]}
]
时间复杂度(O(Tn(F-E))))
(T)为数据组数，(n,F,E)如题意。
1016
给出(n)个数，问哪个数出现了至少((n+1)/2)次。
排个序求出每个数出现了几次即可。
时间复杂度(O(Tnlogn))
(T)为数据组数，(n)为数的个数。
1017
给出(n)个数，找出和最大的递增子序列。
与最长递增子序列类似
(f[i])表示前(i)个数中选了第(i)个数作为结尾的最大和。
[f[i]=max_{j=1}^{j<i}{f[j] (if~~a[i]>a[j])}+a[i]
]
时间复杂度(O(Tn^2))
(T)为数据组数，(n)为数的个数。
1018
有(n)项作业，第(i)项作业要消耗(C)天，(DDL)为第(D)天，每晚于(DDL)一天扣一分。
状态压缩动态规划
只有最多(15)项作业，可以用一个(15)位二进制数表示一个作业完成情况。我们吧这个东西放在动态规划的状态里面，(f[i])表示状态为(i)扣的最少分数。状态转移的时候要预处理很多东西。
[f[i]=min_{p+2^t==iAndAnd pin i}{f[p]+max{0,tim[i]-D[t]}}
]
(tim[i])表示做完(i)集合作业所需的时间。
时间复杂度(O(Tn2^n))
(T)为数据组数，(n)为作业的个数。
代码警告
代码警告
代码警告
代码警告
代码警告
代码警告
代码合集：
//1001
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=5010,maxk=1010;
int N,K,p[maxn];
long long f[3][maxk];
inline int sqr(int x){
return x*x;
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read()+8,K=read();
for(int i=1;i<=K;i++)
p[i]=read();
sort(p+1,p+1+K);
memset(f,10,sizeof(f));
f[K%3][0]=f[(K-1)%3][0]=0;
for(int i=K-2;i>=1;i--){
int a=i%3,b=(i+2)%3,c=(i+1)%3;
for(int j=0;j<=N;j++)
f[a][j]=f[c][j];
for(int j=1;j<=N&&j*3<=K-i+1;j++)
f[a][j]=min(f[a][j],f[b][j-1]+sqr(p[i+1]-p[i]));
}
printf("%I64d
",f[1][N]);
}
return 0;
}
//1002
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=1010;
char A[maxn],B[maxn],C[maxn];
int LA,LB,LC,f[maxn][maxn];
int main(){
//freopen("in","r",stdin);
int T=read();
for(int cas=1;cas<=T;cas++){
scanf("%s%s%s",A+1,B+1,C+1);
LA=strlen(A+1);
LB=strlen(B+1);
LC=strlen(C+1);
for(int i=0;i<=LA;i++)
for(int j=0;j<=LB;j++)
f[i][j]=0;
bool flag=0;
int t;
for(int i=0;i<=LA;i++)
for(int j=0;j<=LB;j++){
if(i){
t=f[i-1][j];
if(t<LC&&C[t+1]==A[i])
f[i][j]=max(f[i][j],t+1);
}
if(j){
t=f[i][j-1];
if(t<LC&&C[t+1]==B[j])
f[i][j]=max(f[i][j],t+1);
}
if(f[i][j]==LC){
flag=1;
goto BRK;
}
}
BRK:;
/*for(int i=1;i<=LA;i++){
for(int j=1;j<=LB;j++)
printf("%d ",f[i][j]);
puts("");
}*/
printf("Data set %d: ",cas);
if(flag)
puts("yes");
else
puts("no");
}
return 0;
}
//1003
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=110;
int N,M,f[maxn][maxn],g[maxn][maxn];
char A[maxn],B[maxn];
void prt(int x,int y){
if(!x&&!y)return;
if(!x){
prt(x,y-1);
printf("%c",B[y]);
}
else if(!y){
prt(x-1,y);
printf("%c",A[x]);
}
else if(g[x][y]==1){
prt(x-1,y);
printf("%c",A[x]);
}
else if(g[x][y]==2){
prt(x,y-1);
printf("%c",B[y]);
}
else{//g[x][y]==0
prt(x-1,y-1);
printf("%c",A[x]);
}
}
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
while(scanf("%s%s",A+1,B+1)!=EOF){
N=strlen(A+1);
M=strlen(B+1);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
f[i][j]=f[i-1][j],g[i][j]=1;
if(f[i][j-1]>f[i][j])
f[i][j]=f[i][j-1],g[i][j]=2;
if(A[i]==B[j]&&f[i-1][j-1]+1>f[i][j])
f[i][j]=f[i-1][j-1]+1,g[i][j]=0;
}
prt(N,M);
puts("");
}
return 0;
}
//1004
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=100010;
int N,h[maxn],f[maxn][21],g[maxn][21];
int main(){
//freopen("in","r",stdin);
while(1){
N=read();
if(!N)break;
for(int i=1;i<=N;i++)
f[i][0]=g[i][0]=h[i]=read();
for(int j=1;j<=20;j++)
for(int i=1;i<=N;i++){
if(i+(1<<j)-1<=N)
f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
if(i-(1<<j)+1>=1)
g[i][j]=min(g[i][j-1],g[i-(1<<j-1)][j-1]);
}
long long ans=0;
for(int i=1;i<=N;i++){
int L=i,R=i;
for(int j=20;j>=0;j--){
if(R+(1<<j)-1<=N&&f[R][j]>=h[i])
R+=(1<<j);
if(L-(1<<j)+1>=1&&g[L][j]>=h[i])
L-=(1<<j);
}
ans=max(ans,1LL*(R-L-1)*h[i]);
//printf("%d %d %d
",i,L,R);
}
printf("%I64d
",ans);
}
return 0;
}
//1005
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=1010;
int N,M,a[maxn][maxn],U[maxn],L[maxn],R[maxn];
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read(),M=read();
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
a[i][j]=(one()=='F');
for(int i=1;i<=M;i++)
U[i]=0;
U[0]=U[M+1]=-1;
int ans=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++)
if(a[i][j])
U[j]++;
else
U[j]=0;
for(int j=1;j<=M;j++){
int k=j;
while(U[j]<=U[k-1])
k=L[k-1];
L[j]=k;
}
for(int j=M;j>=1;j--){
int k=j;
while(U[j]<=U[k+1])
k=R[k+1];
R[j]=k;
}
for(int j=1;j<=M;j++)
ans=max(ans,(R[j]-L[j]+1)*U[j]);
}
printf("%d
",3*ans);
}
return 0;
}
//1006
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=110;
int N,a[maxn][maxn],U[maxn][maxn];
int main(){
//freopen("in","r",stdin);
while(scanf("%d",&N)!=EOF){
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
a[i][j]=(one()=='.');
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(a[i][j])
U[i][j]=U[i-1][j]+1;
else
U[i][j]=0;
int ans=0;
for(int i=1;i<=N;i++)
for(int j=i;j<=N;j++)
for(int k=1;k<=N;k++){
if(U[j][k]<j-i+1)continue;
int p=k;
while(p+1<=N&&U[j][p+1]>=j-i+1)
p++;
int len=p-k+1;
ans+=len*(len+1)/2;
k=p;
}
printf("%d
",ans);
}
return 0;
}
//1007
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=5010;
int N;
int f[2][maxn];
char s[maxn];
int main(){
//freopen("in","r",stdin);
while(scanf("%d",&N)!=EOF){
for(int i=0;i<=N+1;i++)
f[0][i]=f[1][i]=0;
scanf("%s",s+1);
for(int i=N;i>=1;i--)
for(int j=i;j<=N;j++)
if(s[i]==s[j])
f[i&1][j]=f[(i+1)&1][j-1];
else
f[i&1][j]=min(f[i&1][j-1],f[(i+1)&1][j])+1;
printf("%d
",f[1][N]);
}
return 0;
}
//1008
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
const int INF = 1e7;
inline int lowbit(int x) {
return x & (-x);
}
inline int ct(int x) {
int ret = 0;
while (x) {
x -= lowbit(x);
ret++;
}
return ret;
}
bool f[50][50][50][50];
int pre[10][50];
int main() {
//freopen("in", "r", stdin);
int n;
while (scanf("%d", &n) && n) {
memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 4; j++) {
int tmp;
scanf("%d", &tmp);
pre[j][i] = (1 << (tmp - 1)) ^ pre[j][i - 1];
}
int ans = 0;
f[0][0][0][0]=1;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++)
for (int l = 0; l <= n; l++) {
if(!(i+j+k+l))continue;
int cnt = ct(pre[1][i] ^ pre[2][j] ^ pre[3][k] ^ pre[4][l]);
int tmp = i + j + k + l - cnt;
f[i][j][k][l]=0;
if(i)f[i][j][k][l]|=f[i-1][j][k][l];
if(j)f[i][j][k][l]|=f[i][j-1][k][l];
if(k)f[i][j][k][l]|=f[i][j][k-1][l];
if(l)f[i][j][k][l]|=f[i][j][k][l-1];
if (cnt >= 5)
f[i][j][k][l] = false;
ans = max(ans, f[i][j][k][l] ? tmp / 2 : 0);
}
printf("%d
", ans);
}
return 0;
}
//snophy
//1009
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=85,INF=1<<30;
int N,M,f[maxn][maxn],g[maxn][maxn],inc[maxn][maxn];
char A[maxn],B[maxn];
void prt(int x,int y,int v){
if(!(x+y)||!v)return;
if(g[x][y]==4)
prt(x-1,y-1,v);
else if(g[x][y]==3){
prt(x-1,y-1,v-1);
printf("%d Replace %d,%c
",v,x+inc[x][y],B[y]);
}
else if(g[x][y]==2){
prt(x-1,y,v-1);
printf("%d Delete %d
",v,x+inc[x][y]+1);
}
else{//g[x][y]==1
prt(x,y-1,v-1);
printf("%d Insert %d,%c
",v,x+inc[x][y],B[y]);
}
}
int main(){
//freopen("in","r",stdin);
while(scanf("%s%s",A+1,B+1)!=EOF){
N=strlen(A+1);
M=strlen(B+1);
for(int i=0;i<=N;i++)
for(int j=0;j<=M;j++)
f[i][j]=INF;
f[0][0]=0,inc[0][0]=0;
for(int i=1;i<=M;i++)
f[0][i]=i,g[0][i]=1,inc[0][i]=i;
for(int i=1;i<=N;i++)
f[i][0]=i,g[i][0]=2,inc[i][0]=-i;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
f[i][j]=f[i][j-1]+1,g[i][j]=1,inc[i][j]=inc[i][j-1]+1;
if(f[i][j]>f[i-1][j]+1)
f[i][j]=f[i-1][j]+1,g[i][j]=2,inc[i][j]=inc[i-1][j]-1;
if(A[i]==B[j]&&f[i][j]>f[i-1][j-1])
f[i][j]=f[i-1][j-1],g[i][j]=4,inc[i][j]=inc[i-1][j-1];
else if(f[i][j]>f[i-1][j-1]+1)
f[i][j]=f[i-1][j-1]+1,g[i][j]=3,inc[i][j]=inc[i-1][j-1];
}
printf("%d
",f[N][M]);
prt(N,M,f[N][M]);
/*for(int i=0;i<=N;i++){
for(int j=0;j<=M;j++)
printf("%3d ",f[i][j]);
puts("");
}
puts("");
for(int i=0;i<=N;i++){
for(int j=0;j<=M;j++)
printf("%3d ",g[i][j]);
puts("");
}
puts("");
for(int i=0;i<=N;i++){
for(int j=0;j<=M;j++)
printf("%3d ",inc[i][j]);
puts("");
}
puts("");*/
}
return 0;
}
//1010
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=10010,MOD=19260817;
char s[maxn];
int N,M,f[maxn],len[maxn];
char dict[26][6]={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
char word[maxn][25];
int Hash[maxn],Hword[maxn],pow2[maxn];
inline int get_hash(int L,int R){
return ((Hash[R]-1LL*Hash[L-1]*pow2[R-L+1])%MOD+MOD)%MOD;
}
int main(){
//freopen("in","r",stdin);
pow2[0]=1;
for(int i=1;i<maxn;i++)
pow2[i]=(pow2[i-1]*2)%MOD;
for(int _=read();_;_--){
scanf("%s",s+1);
M=strlen(s+1);
for(int i=1;i<=M;i++){
int c=0;
if(s[i]=='-')c=1;
Hash[i]=(Hash[i-1]*2+c)%MOD;
}
N=read();
for(int i=1;i<=N;i++){
scanf("%s",word[i]+1);
len[i]=0;Hword[i]=0;
for(int j=1;word[i][j];j++){
len[i]+=strlen(dict[word[i][j]-'A']);
for(int k=0;dict[word[i][j]-'A'][k];k++){
int c=0;
if(dict[word[i][j]-'A'][k]=='-')c=1;
Hword[i]=(Hword[i]*2+c)%MOD;
}
}
}
f[0]=1;
for(int i=1;i<=M;i++){
f[i]=0;
for(int j=1;j<=N;j++)
if(i>=len[j]&&get_hash(i-len[j]+1,i)==Hword[j])
f[i]+=f[i-len[j]];
}
printf("%d
",f[M]);
}
return 0;
}
//1010MLE代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=10010,maxm=10000*20*4+10;
char s[maxn];
int N,f[maxn];
char dict[26][6]={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
int ch[maxm][2],fail[maxm],cnt,Len[maxn];
vector<int>End[maxm];
void clear(){
cnt=0;
memset(ch[0],0,sizeof(ch));
fail[0]=0;
}
void ins(char *s,int id){
int now=0;Len[id]=0;
for(int i=1;s[i];i++){
for(int j=0;dict[s[i]-'A'][j];j++){
int c=0;
if(dict[s[i]-'A'][j]=='-')
c=1;
//printf("%c",dict[s[i]-'A'][j]);
if(!ch[now][c]){
ch[now][c]=++cnt;
memset(ch[cnt],0,sizeof(ch[cnt]));
fail[cnt]=0;
End[cnt].clear();
}
now=ch[now][c];
Len[id]++;
}
}
End[now].push_back(id);
//printf("%d %d
",now,id);
//puts("");
}
int q[maxm],head,tail;
void bfs_build(){
head=1,tail=0;
for(int i=0;i<2;i++)
if(ch[0][i])
q[++tail]=ch[0][i];
for(;head<=tail;head++){
int x=q[head];
for(int i=0;i<2;i++)
if(ch[x][i]){
fail[ch[x][i]]=ch[fail[x]][i];
q[++tail]=ch[x][i];
}
else
ch[x][i]=ch[fail[x]][i];
}
}
void solve(){
for(int i=1;i<=tail;i++){
int siz=End[fail[q[i]]].size();
for(int j=0;j<siz;j++)
End[q[i]].push_back(End[fail[q[i]]][j]);
}
}
void query(char *s){
int cur=0;f[0]=1;
for(int i=1;i<=N;i++){
f[i]=0;
int c=0;
if(s[i]=='-')
c=1;
cur=ch[cur][c];
int siz=End[cur].size();
for(int j=0;j<siz;j++)
f[i]+=f[i-Len[End[cur][j]]];
}
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
scanf("%s",s+1);
N=strlen(s+1);
clear();
char tmp[25];
for(int _=read();_;_--){
scanf("%s",tmp+1);
ins(tmp,_);
}
bfs_build();
solve();
query(s);
printf("%d
",f[N]);
}
return 0;
}
//1011
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=65,maxk=7;
int N,K;
long long f[maxn][maxk][maxk];
int main(){
//freopen("in","r",stdin);
while(scanf("%d%d",&N,&K)!=EOF){
f[0][0][0]=1;
for(int i=1;i<=N;i++)
for(int j=0;j<=K;j++)
for(int k=0;k<=K;k++){
f[i][j][k]=0;
if(j){
if(!k)
f[i][j][k]+=f[i-1][j-1][k];
if(k<K)
f[i][j][k]+=f[i-1][j-1][k+1];
}
if(k){
if(!j)
f[i][j][k]+=f[i-1][j][k-1];
if(j<K)
f[i][j][k]+=f[i-1][j+1][k-1];
}
/*if(f[i][j][k])
printf("%d %d %d %d
",i,j,k,f[i][j][k]);*/
}
long long ans=0;
for(int j=0;j<=K;j++)
for(int k=0;k<=K;k++)
ans+=f[N][j][k];
printf("%I64d
",ans);
}
return 0;
}
//1012
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=1010;
int N,M,X,Y,a[maxn][maxn],sum[maxn][maxn];
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read(),M=read(),X=read(),Y=read();
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
a[i][j]=read(),sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
int ans=0;
for(int i=X;i<=N;i++)
for(int j=Y;j<=M;j++)
ans=max(ans,sum[i][j]-sum[i-X][j]-sum[i][j-Y]+sum[i-X][j-Y]);
printf("%d
",ans);
}
return 0;
}
//1013
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=55,maxm=50*50*100+10;
int N,v[maxn],p[maxn],sum;
bool f[maxm];
int main(){
//freopen("in","r",stdin);
while(1){
N=read();sum=0;
if(N<0)break;
for(int i=1;i<=N;i++)
v[i]=read(),p[i]=read(),sum+=v[i]*p[i];
for(int i=1;i<=sum/2;i++)
f[i]=0;
f[0]=1;
int ans=0;
for(int i=1;i<=N;i++)
for(int j=1;j<=p[i];j++)
for(int k=sum/2;k>=j*v[i];k--)
if(f[k-j*v[i]])
f[k]=1,ans=max(ans,k);
printf("%d %d
",sum-ans,ans);
}
return 0;
}
//1014
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=10010;
int N,M,w[maxn];
double v[maxn];
double f[maxn];
int main(){
//freopen("in","r",stdin);
while(1){
N=read(),M=read();
if(N+M==0)break;
for(int i=0;i<=N;i++)
f[i]=-1;
for(int i=1;i<=M;i++)
w[i]=read(),scanf("%lf",&v[i]);
f[0]=0;
for(int i=1;i<=M;i++)
for(int j=N;j>=w[i];j--)
if(f[j-w[i]]>=0)
f[j]=max(f[j],f[j-w[i]]+(1-f[j-w[i]])*v[i]);
double ans=0;
for(int i=0;i<=N;i++)
ans=max(ans,f[i]);
printf("%.1lf%%
",ans*100);
}
return 0;
}
//1015
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=510,maxm=10010,INF=1<<30;
int N,M,f[maxm],w[maxn],p[maxn];
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
M=read()-read();
N=read(),M=-M;
for(int i=1;i<=N;i++)
p[i]=read(),w[i]=read();
for(int i=1;i<=M;i++)
f[i]=INF;
for(int i=1;i<=N;i++)
for(int j=w[i];j<=M;j++)
f[j]=min(f[j],f[j-w[i]]+p[i]);
if(f[M]==INF)
puts("This is impossible.");
else
printf("The minimum amount of money in the piggy-bank is %d.
",f[M]);
}
return 0;
}
//1016
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=1000010;
int N,a[maxn];
int main(){
//freopen("in","r",stdin);
while(scanf("%d",&N)!=EOF){
for(int i=1;i<=N;i++)
a[i]=read();
sort(a+1,a+1+N);
for(int i=1;i<=N;){
int j=i;
while(j<=N&&a[i]==a[j])
j++;
if(j-i>=(N+1)/2){
printf("%d
",a[i]);
break;
}
i=j;
}
}
return 0;
}
//1017
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=1010;
int N,a[maxn];
long long f[maxn];
int main(){
//freopen("in","r",stdin);
while(1){
N=read();
if(!N)break;
for(int i=1;i<=N;i++)
a[i]=read();
long long ans=0;
for(int i=1;i<=N;i++){
f[i]=a[i];
for(int j=1;j<i;j++)
if(a[i]>a[j])
f[i]=max(f[i],f[j]+a[i]);
ans=max(ans,f[i]);
}
printf("%I64d
",ans);
}
return 0;
}
//1018
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=15;
const long long INF=1LL<<60;
int N,d[maxn],c[maxn],g[1<<maxn],lin[1<<maxn],rk[maxn];
char s[maxn][110];
long long f[1<<maxn],tim[1<<maxn];
inline bool cmp(int x,int y){
for(int i=0;;i++)
if(s[x][i]!=s[y][i])
return s[x][i]<s[y][i];
return 0;
}
inline int lowbit(int x){return x&-x;}
void print(int x){
if(!x)return;
print(x-(1<<g[x]));
printf("%s
",s[g[x]]);
}
int main(){
for(int i=0;i<maxn;i++)
lin[1<<i]=i;
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read();
for(int i=0;i<N;i++){
scanf("%s",s[i]);
d[i]=read(),c[i]=read();
rk[i]=i;
}
sort(rk,rk+N,cmp);
for(int i=1;i<(1<<N);i++)
tim[i]=tim[i-lowbit(i)]+c[lin[lowbit(i)]];
for(int i=0;i<(1<<N);i++)
f[i]=INF;
f[0]=0;
for(int i=1;i<(1<<N);i++){
int j=i;
while(j){
int t=lin[lowbit(j)];
int p=i-(1<<t);
if(f[i]>f[p]+max(0LL,tim[i]-d[t]))
f[i]=f[p]+max(0LL,tim[i]-d[t]),g[i]=t;
else if(f[i]==f[p]+max(0LL,tim[i]-d[t]))
if(rk[g[i]]<rk[t])
g[i]=t;
j-=lowbit(j);
}
}
printf("%I64d
",f[(1<<N)-1]);
print((1<<N)-1);
}
return 0;
}