176

/*
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 11;
int n;
int state[N]={0};//第i列是否已经有皇后 state[j]=1=>第i列已经有皇后
int ans[N]={0};
bool check(int row,int column)
{
for(int i=1;i<=row;i++)
{

if(column+row==ans[i]+i) return false;//右斜向上
if(row-column==i-ans[i]) return false;//左斜向上
}
return true;
}
void dfs(int u )//传入行
{

if(u==n+1)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(ans[i]==j)
printf("Q");
else
printf(".");
}
printf("\n");
}
puts("");
return;
}
for(int j=1;j<=n;j++)//对第u行遍历j列
{
if(state[j])
continue;
if(check(u,j))//左斜上对角线和右斜上对角线没有皇后
{
ans[u]=j;
state[j]=1;
dfs(u+1);
state[j]=0;
}
}
}

int main()
{
cin>>n;
dfs(1);
return 0;
}
*/

#include<cstdio>
#include<ctime>
#include<iostream>
using namespace std;

int n;
int cnt = 0;//cnt存储方案个数
int ans[14] = {0};
int usedc[14] = { 0 };

bool check(int row, int column)
{
int i;
for (i = 1; i < row; i++)
{
if ((i + ans[i]) == row + column) return false;
if ((i - ans[i]) == row - column) return false;
}

return true;
}

void dfs(int siden)
{
if (siden == n + 1)
{
cnt++;
for (int v = 1; v <= n; v++)
{
for(int x=1;x<=n;x++)
{
if(ans[v]==x)
printf("Q");
else
printf(".");
}
printf("\n");
}
puts("");
return;
}
for (int k = 1; k <= n; k++)
{
if (usedc[k])
continue;
if (check(siden, k))
{

ans[siden] = k;
usedc[k] = 1;
dfs(siden + 1);
usedc[k] = 0;
}
}
}
int main()
{

cin >> n;
dfs(1);
return 0;
}


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 11;
int n;
int ans[N];
bool state[N];
void dfs(int u )
{
if(u==n+1)
{
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
printf("\n");
return;
}
for(int i=1;i<=n;i++)
{
if(!state[i])
{
ans[u]=i;
state[i]=true;
dfs(u+1);
state[i]=false;

}
}
}

int main()
{
cin>>n;
dfs(1);
return 0;
}



#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
cin >> n >> p + 1 >> m >> s + 1;

for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}

for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == n)
{
printf("%d ", i - n);
j = ne[j];
}
}

return 0;
}



#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
int tt = -1, hh=0;//hh队列头 tt队列尾
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i = 0; i <n; i ++) cin>>a[i];
for(int i = 0; i < n; i ++)
{
//维持滑动窗口的大小
//当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
//滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
if(hh <= tt && k < i - q[hh] + 1) hh ++;
//构造单调递增队列
//当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
//就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++ tt] = i;
}
puts("");
/*
hh = 0,tt = -1;
for(int i = 0; i < n; i ++)
{
if(hh <= tt && k < i - q[hh] + 1) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k ) printf("%d ", a[q[hh]]);
}
*/
return 0;
}


#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
int tt = -1, hh=0;//hh队列头 tt队列尾
cin.tie(0);
cin>>n>>k;
for(int i = 0; i <n; i ++) cin>>a[i];
for(int i = 0; i < n; i ++)
{
//维持滑动窗口的大小
//当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
//滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
if(hh <= tt && k < i - q[hh] + 1) hh ++;
//构造单调递增队列
//当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
//就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k) printf("%d ", a[q[hh]]);

//printf("%d    %d\n",hh,tt);
//for(int j=hh;j<=tt;j++)printf("~%d",a[q[j]]);
//printf("\n");
}
puts("");
hh = 0,tt = -1;
for(int i = 0; i < n; i ++)
{
if(hh <= tt && k < i - q[hh] + 1) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k ) printf("%d ", a[q[hh]]);
}
return 0;
}


#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=110;
int n,m;
int v[N],w[N],s[N]; //V体积 w价值 s个数
int f[N][N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];//一行同时输入的v w
for(int i=1;i<=n;i++) //物品
{
for(int j=1;j<=m;j++) //限制 本题是体积v
{
for(int k=0;k*v[i]<=j&&k<=s[i];k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);

}
}
cout<<f[n][m];
return 0;
}


#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
/*
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N][N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
for(int i=1;i<=n;i++) //物品
{
for(int j=1;j<=m;j++) //限制 本题是体积v
{
for(int k=0;k*v[i]<=j;k++)
//不选的情况一定存在 但选该物品的情况 不一定存在
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);

}
}
cout<<f[n][m];
return 0;
}

*/
//优化1-》类似01背包
//优化2 -》类似01背包问题的优化方法
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
for(int i=1;i<=n;i++) //物品
{
for(int j=v[i];j<=m;j++) //限制 本题是体积v
{
f[j]=max(f[j],f[j-v[i]]+w[i]);//优化前的f【i】【x】是同一个i
}
}
cout<<f[m];
return 0;
}



#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
/*
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N][N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
for(int i=1;i<=n;i++) //物品
{
for(int j=1;j<=m;j++) //限制 本题是体积v
{
//不选的情况一定存在 但选该物品的情况 不一定存在
f[i][j]=f[i-1][j];
if(j>=v[i])//当体积可以装得下物品i的时候 选该物品的情况才存在
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}
*/
//优化成1维数组：f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
//①f[i][x]这一层只用到了f[i],f[i-1] 更小的没用到 只有两层 所以用先-后 来记录这i-1 i
//②第二维度都小于等于j
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N];//去掉第一位

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
for(int i=1;i<=n;i++) //物品
{
for(int j=m;j>=v[i];j--) //限制 本题是体积v
{
f[j]=max(f[j],f[j-v[i]]+w[i]);//第一层小的先更新 所以,f[j-v[i]]+w[i]相当于是第[i-1]层的
}
}
cout<<f[m];
return 0;
}




//集合：f[i,j]//所有在A[1...i]和B[1...j]中都出现过 且以B[j]结尾的公共上升子序列的集合
//属性:max
//状态切割①f[i-1,j]
//②f[i-1,r]+1;
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

const int N=3010;
int n;
int a[N],b[N];
int f[N][N];

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++)
for(int j=1;j<=n;j++)//固定A
{
f[i][j]=f[i-1][j];//a[i]不在公共最长上升子序列里
if(a[i]==b[j])
{
int maxn=1;
for(int k=1;k<j;k++)
{
if(b[k]<a[i])maxn=max(maxn,f[i-1][k]+1);
}
f[i][j]=max(maxn,f[i][j]);
}
}
*/
for(int i=1;i<=n;i++)
//固定A
{
int maxv=1;
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];//a[i]不在公共最长上升子序列里
if(a[i]==b[j])//a[i]==b[j]) a[i]可能在公共上升子序列里
{
f[i][j]=max(maxv,f[i][j]);//不在和在了的比较
}
if(b[j]<a[i])maxv=max(maxv,f[i-1][j]+1);//若b[j]<a[i] 这是f【i，x】
//则b[j]可以在f[i,j]里 比较b[j]在与不在的大小
}
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(f[n][i],ans);

cout<<ans;
return 0;
}


1个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int a[N];
int up[N], down[N];
int ans;

void dfs(int u, int su, int sd)//当前搜索的下标u  上升子序列的长度su  下降子序列的长度sd
{
if (su + sd >= ans) return;//剪枝 比已有的答案还大 不符合
if (u == n)//遍历到最后一个数了
{
ans = min(ans, su + sd);
return;
}
//情况1 安排给上升子序列
int k = 0;
while (k < su && up[k] >= a[u]) k ++ ;
if (k < su)//安排给第k个子序列
{
int t = up[k];//记录第k个子序列的最后一个数 up[k]
up[k] = a[u];//更新为a[u]
dfs(u + 1, su, sd);
up[k] = t;
}
else//新开一个子序列
{
/*
当前dfs中维护的区间下标是0 ~ su - 1和0 ~ sd - 1
所以如果我们在下一层中修改下标是su或者sd的数，对当前dfs节点没有任何影响，所以不需要回溯。
*/
up[k] = a[u];
dfs(u + 1, su + 1, sd);
}
//情况2 安排给下降子序列
k = 0;
while (k < sd && down[k] <= a[u]) k ++ ;
if (k < sd)
{
int t = down[k];
down[k] = a[u];
dfs(u + 1, su, sd);
down[k] = t;
}
else
{
down[k] = a[u];
dfs(u + 1, su, sd + 1);
}
}

int main()
{
while (cin >> n, n)
{
for (int i = 0; i < n; i ++ ) cin >> a[i];

ans = n;//最差情况 每一个数都是一个子序列 答案为ans
dfs(0, 0, 0);

cout << ans << endl;
}

return 0;
}