2658

2020-07-02 07:49

2020-06-30 08:04
for(int len = 1; len <= n; len++) {
//枚举连续区间的长度
for(int l = 0; l + len - 1 < n; l++) {
//连续区间的开始节点
int r = l + len - 1;
//连续区间的右端点
for(int j = r + 1; j < n; j++) {
//枚举选择插入的位置
memcpy(w[depth], q, sizeof q);
int y = l;
** for(int x = r+1; x <= j; x++, y++) q[y] = w[depth][x];
for(int x = l; x <= r; x++, y++) q[y] = w[depth][x];**
//切换两段数据单元
if(dfs(depth+1, max_depth)) return true;
memcpy(q, w[depth], sizeof q);
}
}
}

2020-06-28 01:37
903昂贵的聘礼： 误用不合法的路径修改dis，导致答案变小，血一般的教训。

2020-06-27 08:17

RT
QAQ

2020-06-27 08:15
// common
# include <iostream>
# include <cstdio>
# include <cmath>
using namespace std;
int n,ans;
int a[3010],b[3010];
int f[3010][3010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
//f[i][j]表示到i以j未结尾的最长LICS
//回想LIS LCS
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(a[i]!=b[j]) f[i][j]=f[i-1][j]; //继承
else{
for(int k=0;k<j;k++)
if(b[k]<b[j])
f[i][j]=max(f[i][j],f[i-1][k]+1);
}
}
for(int i=1;i<=n;i++)
ans=max(ans,f[n][i]);   //必须
printf("%d",ans);
return 0;
}
// dynamic
# include <iostream>
# include <cstdio>
# include <cmath>
using namespace std;
int n,ans;
int a[3010],b[3010];
int f[3010][3010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
int val=0;
for(int j=1;j<=n;j++){
if(a[i]!=b[j]) f[i][j]=f[i-1][j];
else f[i][j]=val+1;
if(b[j]<a[i]) val=max(val,f[i-1][j]);
// 避免重复扫描
}
}
for(int i=1;i<=n;i++)
ans=max(ans,f[n][i]);
printf("%d",ans);
return 0;
}

2020-06-26 08:21

2020-06-19 10:04

# include <iostream>
# include <cstdio>
using namespace std;
int n;
int a[310],num[65],num2[65];
void dfs(int x,int y,int lim){
/*if(lim==1){
printf("%d\n",y);
}*/
if(x>lim) return ;
if(y>n){
printf("%d",lim);
exit(0);
}
bool p=0;
for(int i=y;i<=n;i++)
if(num[a[i]]>0){
p=1;
break;
}
if(!p){
printf("%d",lim);
exit(0);
}
if(num[a[y]]<=0) dfs(x,y+1,lim);
num[a[y]]--;
for(int i=a[y]+1;i<=59;i++){
int flag2=0;
if(num[i]<=0) continue;
int e=i-a[y];
for(int j=i;j<=59;j+=e){
if(num[j]<=0){
flag2=j;
break;
}
else
num[j]--;
}
if(flag2!=0){
for(int j=i;j<flag2;j+=e)
num[j]++;
continue;
}
dfs(x+1,y+1,lim);
for(int j=i;j<=59;j+=e)
num[j]++;
}
num[a[y]]++;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),num[a[i]]++,num2[a[i]]=num[a[i]];
for(int i=1;i<=16;i++){
cout<<i<<endl;
dfs(0,1,i);
for(int i=0;i<=59;i++)
num[i]=num2[i];
}
cout<<17;
return 0;
}

ans:

# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
struct node{
int l,d,num;
}rode[2100];
int n,cnt;
int a[310],qua[60];
bool cmp(node a,node b){
return a.num>b.num;
}
bool check(int x,int y){
for(int i=x;i<=59;i+=y)
if(!qua[i])
return 0;
return 1;
}
void dfs(int x,int sum,int sta,int lim){
//printf("%d\n",sta);
if(sum==n){
printf("%d",lim);
exit(0);
}
if(x>=lim) return ;
if(sum+rode[sta].num*(lim-x)<n) return ;
for(int i=sta;i<=cnt;i++){
if(rode[i].num>n-x) continue;
if(!check(rode[i].l,rode[i].d)) continue;
for(int j=rode[i].l;j<=59;j+=rode[i].d)
qua[j]--;
dfs(x+1,sum+rode[i].num,i,lim);
for(int j=rode[i].l;j<=59;j+=rode[i].d)
qua[j]++;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),qua[a[i]]++;
for(int i=0;i<=58;i++)
for(int j=i+1;i+j<=59;j++){
if(check(i,j))
rode[++cnt].l=i,rode[cnt].d=j,rode[cnt].num=(59-i)/j+1;
}
sort(rode+1,rode+cnt+1,cmp);
/*  for(int i=1;i<=cnt;i++)
if(rode[i].l==0)
printf("%d %d %d\n",rode[i].l,rode[i].d,rode[i].num);*/
for(int i=1;i<=16;i++)
dfs(0,0,1,i);
printf("17");
return 0;
}

2020-06-19 08:48

# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <map>
using namespace std;
struct node{
string s;
int x;
};
queue<node> q1,q2;
map<string,int> m1,m2,M1,M2;
string s0,s1;
string s[11],S[11];
int cnt=1,num=0;
int main(){
cin>>s0>>s1;
while(cin>>s[cnt]>>S[cnt]){
++cnt;
if(cnt>6) break;
}
q1.push((node){s0,0});
q2.push((node){s1,0});
M2[s1]=M1[s0]=0;
m1[s0]=m2[s1]=1;
while(!q1.empty()&&!q2.empty()){  //此处可以用&，因为如果出现合法情况，是一半一半的情况，如果是||那么就爆炸了。。
/*num++;
if(num>10000)
break;*/
//if(!q1.empty()){
node t=q1.front();q1.pop();
string ss=t.s;
//cout<<ss<<" "<<endl;
//cout<<t.x<<" ";
int l=ss.length();
if(t.x>10){
return 0;
}
for(int i=1;i<cnt;i++)
for(int j=0;j<l;j++){  // 不一定是替换第一次出现的
string SS=ss;
int e=SS.find(s[i],j);
if(e>=0&&e<l){
string sss=SS.replace(e,s[i].length(),S[i]);
if(m2[sss]==1){
printf("%d",t.x+M2[sss]+1);
return 0;
}
if(m1[sss]!=1)
q1.push((node){sss,t.x+1}),m1[sss]=1,M1[sss]=t.x+1;
}
}
// }
//if(!q2.empty()){
t=q2.front();q2.pop();
ss=t.s;
//cout<<t.x<<endl;
l=ss.length();
if(t.x>10){
return 0;
}
for(int i=1;i<cnt;i++)
for(int j=0;j<l;j++){  // 不一定是替换第一次出现的
string SS=ss;
int e=SS.find(S[i],j);
if(e>=0&&e<l){
string sss=SS.replace(e,S[i].length(),s[i]);
if(m1[sss]==1){
printf("%d",t.x+M1[sss]+1);
return 0;
}
if(m2[sss]!=1)
q2.push((node){sss,t.x+1}),m2[sss]=1,M2[sss]=t.x+1;
}
}
//}
}
return 0;
}

2020-06-18 07:46
bfs即可

2020-06-18 07:42
bfs即可