给出n个数，zjm想找出出现至少(n+1)/2次的数， 现在需要你帮忙找出这个数是多少？
本题包含多组数据：
每组数据包含两行。
第一行一个数字N(1<=N<=999999) ，保证N为奇数。
第二行为N个用空格隔开的整数。
数据以EOF结束。
5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1
对于每一组数据，你需要输出你找到的唯一的数。
3
5
1
1.利用桶排的思想 记录下每种数字的个数
2.遍历整个桶 当到达一个数字的个数>=(n+1)/2 时 将其输出并break(只可能有一个数符合条件)
emmm无
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<map>
#define MAXN 1000010
using namespace std;
int n;
int a[MAXN];
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
int x;
for(int i=1;i<=n;i++)
{
cin>>x;
a[x]++;
}
for(int i=1;i<=MAXN;i++) if(a[i]>=(n+1)/2) {cout<<i<<endl;break;}
}
system("pause");
return 0;
}
zjm被困在一个三维的空间中,现在要寻找最短路径逃生！
空间由立方体单位构成。
zjm每次向上下前后左右移动一个单位需要一分钟，且zjm不能对角线移动。
空间的四周封闭。zjm的目标是走到空间的出口。
是否存在逃出生天的可能性？如果存在，则需要多少时间？
输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为L，R和C（皆不超过30）。
L表示空间的高度，R和C分别表示每层空间的行与列的大小。
随后L层，每层R行，每行C个字符。
每个字符表示空间的一个单元。’#‘表示不可通过单元，’.‘表示空白单元。
zjm的起始位置在’S’，出口为’E’。每层空间后都有一个空行。
L，R和C均为0时输入结束。
3 4 5
S….
.###.
.##..
###.#
#####
#####
##.##
##…
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
每个空间对应一行输出。
如果可以逃生，则输出如下
Escaped in x minute(s).
x为最短脱离时间。
如果无法逃生，则输出如下
Trapped!
Escaped in 11 minute(s).
Trapped!
1.将图首先进行初始化 并存到三维数组中 并且记录S 与 E 的位置
2.以S点为起点进行一个BFS 只不过变成了三维上的递推
注意一下边界条件的判断即可
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<map>
#include<queue>
#define MAXN 100
#define INF 0x7fffff
using namespace std;
int sx[]={1,-1,0,0,0,0};
int sy[]={0,0,1,-1,0,0};
int sz[]={0,0,0,0,1,-1};
int h,n,m;
int a[MAXN][MAXN][MAXN];
int v[MAXN][MAXN][MAXN];
int dis[MAXN][MAXN][MAXN];
struct node
{
int x,y,z;
}s,t;
char c;
bool check(int dx,int dy,int dz)
{
if(dx<1||dx>n||dy<1||dy>m||dz<1||dz>h) return false;
return true;
}
void bfs()
{
queue<node> q;
q.push(s);
v[s.x][s.y][s.z]=1;
dis[s.x][s.y][s.z]=0;
while(!q.empty())
{
node u=q.front();q.pop();
for(int i=0;i<6;i++)
{
int dx=u.x+sx[i],dy=u.y+sy[i],dz=u.z+sz[i];
if(!check(dx,dy,dz)||v[dx][dy][dz]) continue;//越界或已被访问过
if(a[dx][dy][dz]==0) continue;//不可通过
dis[dx][dy][dz]=dis[u.x][u.y][u.z]+1;
v[dx][dy][dz]=1;
node cur;
cur.x=dx;cur.y=dy;cur.z=dz;
q.push(cur);
}
}
}
int main()
{
while(true)
{
cin>>h>>n>>m;
if(h==0&&n==0&&m==0) break;
memset(a,0,sizeof(a));
memset(v,0,sizeof(v));
memset(dis,-1,sizeof(dis));
int tnt=0;
for(int k=1;k<=h;k++)//输入及预处理
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>c;
tnt++;
if(c=='#') a[i][j][k]=0;
else if(c=='.') a[i][j][k]=1;
else if(c=='S'){a[i][j][k]=1;s.x=i;s.y=j;s.z=k;}
else if(c=='E'){a[i][j][k]=1;t.x=i;t.y=j;t.z=k;}
}
bfs();
if(dis[t.x][t.y][t.z]==-1) cout<<"Trapped!"<<endl;
else cout<<"Escaped in "<<dis[t.x][t.y][t.z]<<" minute(s)."<<endl;
}
system("pause");
return 0;
}
东东每个学期都会去寝室接受扫楼的任务，并清点每个寝室的人数。
每个寝室里面有ai个人(1<=i<=n)。从第i到第j个宿舍一共有sum(i,j)=a[i]+…+a[j]个人
这让宿管阿姨非常开心，并且让东东扫楼m次，每一次数第i到第j个宿舍sum(i,j)
问题是要找到sum(i1, j1) + … + sum(im,jm)的最大值。且ix <= iy <=jx和ix <= jy <=jx的情况是不被允许的。也就是说m段都不能相交。
注：1 ≤ i ≤ n ≤ 1e6 , -32768 ≤ ai ≤ 32767 人数可以为负数。。。。(1<=n<=1000000)
输入m，输入n。后面跟着输入n个ai
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
输出最大和
6
8
1.理解了题意后便会发现,这是一个最大m段子序列和问题 且提示了需要用DP做 于是我们来考虑如何DP
2.定义dp[i][j]为前j个数取出i段得到的最大值，那么状态转移方程为dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][k]+a[j]) ， i-1<=k<=j-1
也就是说有两种不同的选择：第一个是第j个数连在第j-1个数所在的段的后面，第二个是第j个为新的一段的第一个数字。
但是这样的复杂度为O(n^3) 我们考虑如何优化他
3.我们会发现dp[i-1][j]的值只会在计算dp[i][j]时用到，于是可以降维，用一维的DP数组来存储
同时计算max(dp[i-1][k])时 也可以在之前的计算中记录下来 这样就可以实现很大的优化
4.用pre[j]表示前一个状态中1–j的dp的最大值，就变成 dp[j] = max(dp[j-1] + a[j] ,pre[j-1]+a[j])
对于这种求最优值的问题 DP是一个很好的算法 问题的关键就是如何构造dp[]数组 以及状态转移方程的构造(必要时候还需要进行降维)
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<map>
#include<queue>
#define MAXN 1000010
#define INF 0x3f3f3f3f
using namespace std;
int a[MAXN],dp[MAXN],pre[MAXN];
int m,n,maxx;
int main()
{
while(~scanf("%d%d",&m,&n))
{
memset(dp,0,sizeof(dp));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
maxx=-INF;
for(int j=i;j<=n;j++)
{
dp[j]=max(dp[j-1],pre[j-1])+a[j];//dp[j-1]+a[j]表示将a[j]加到第i段序列的末尾 pre[j-1]+a[j]表示a[j]新成一段
pre[j-1]=maxx;//pre[j]表示前一个状态中1–j的dp的最大值
if(dp[j]>maxx) maxx=dp[j];
}
}
cout<<maxx<<endl;
}
system("pause");
return 0;
}
给定一个只由’[’ ‘(’ ‘)’ ']'组成的字符串,且
定义一个合法的括号序列
• 1. 空序列合法
• 2. S合法，那么(S)和[S]合法
• 3. 假设A和B合法，那么AB合法
• 合法序列 - (), [], (()), ([]), ()[], ()[()]
• 非法序列 - (, [, ], )(, (]), ([()，([)]
求这个字符串中 最长的合法序列的长度
若干个字符串 以"end"结尾
((()))
()()()
([]])
)[)(
([][][)
end
最长括号匹配序列的长度
6
6
4
0
6
一个很经典的区间DP的问题
1.定义dp[i][j] 为区间[i,j]内最长的合法序列的长度
2.状态转移方程:
对于一个len>=2的区间S 如果区间形如 ( S0 ) 或者 [ S0 ] 那么dp[i][j]=dp[i+1][j-1]+2
否则 区间[i,j]的值可以从子问题中更新过来（因为长度小于len的子串的答案值已经被计算过了）
即dp[i][j]=max(dp[l][k]+dp[k+1][j]) i<=k<j
3.输出答案
答案即存储在dp[0][s.length()]中
很经典的区间DP题
写完这道题 感觉对区间DP的思路有了更深入的理解
更熟悉了这种先枚举 len 再枚举左端点的思路
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<map>
#include<queue>
using namespace std;
string s;
int dp[1010][1010];
int main()
{
while(true)
{
cin>>s;
memset(dp,0,sizeof(dp));
if(s.compare("end")==0) break;
//dp[i][j] 表示 区间[i,j]的最大括号匹配数
for(int len=2;len<=s.length();len++)
{
for(int i=0;i<s.length()-len+1;i++)
{
int l=i,r=i+len-1;
for(int k=l;k<r;k++)
{
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);//由子问题更新而来
}
if((s[l]=='['&&s[r]==']')||(s[l]=='('&&s[r]==')'))
{
if(len==2) dp[l][r]=2;
else dp[l][r]=max(dp[l][r],dp[l+1][r-1]+2);
}
}
}
cout<<dp[0][s.length()-1]<<endl;
}
system("pause");
return 0;
}
马上假期就要结束了，zjm还有 n 个作业，完成某个作业需要一定的时间，而且每个作业有一个截止时间，若超过截止时间，一天就要扣一分。
zjm想知道如何安排做作业，使得扣的分数最少。
Tips: 如果开始做某个作业，就必须把这个作业做完了，才能做下一个作业。
有多组测试数据。第一行一个整数表示测试数据的组数
第一行一个整数 n(1<=n<=15)
接下来n行，每行一个字符串(长度不超过100) S 表示任务的名称和两个整数 D 和 C，分别表示任务的截止时间和完成任务需要的天数。
这 n 个任务是按照字符串的字典序从小到大给出。
2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3
每组测试数据，输出最少扣的分数，并输出完成作业的方案，如果有多个方案，输出字典序最小的一个。
2
Computer
Math
English
3
Computer
English
Math
1.虽然数据的规模很小,但是却有2^15-1种方案 面对这么多方案 我们可以用状压的思路进行DP
把每一个任务做与不做用 0/1表示 第i位为1表示该状态中已经做了该任务
2.定义一个一位数组f[] f[S]表示在S这个状态时最少罚的分数 S是被2进制压缩后的十进制数
3.首先i从状态000···1遍历到111···1 即从1到1<<n-1
然后j从task[0]遍历到task[n-1] 查看是否可以通过最后做第j件事 使得从某个状态S0转移到当前的状态i
如果可以我们就计算罚的分数 如果可以使当前的值更优 则更新并把最后一件干的事记录到pre[S]中
4最后,最少罚的分数即在f[1<<n-1]中
如何输出方案呢？
pre[S]中记录了到达S这个状态时最后做的任务的下标 我们只需进行一次回溯即可
第一次接触状压DP,发现状压DP的这种把状态压缩成二进制的方法很神奇 也很有用
尤其是面对这种数据规模很小 但是状态数却很多的情况
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<map>
#include<queue>
#define INF 0x7fffffff
using namespace std;
int f[50010],t[50010],pre[50010];//f[S]表示在S这一状态下扣的最少分 t[S]表示花的时间
struct course
{
string name;
int ddl;
int expends;
}task[100];
void output(int x)
{
if(x==0) return;//如果所有任务都处理了 就返回
output(x-(1<<pre[x]));
cout<<task[pre[x]].name<<endl;
}
int T,n;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
memset(f,0,sizeof(f));
for(int i=0;i<n;i++) cin>>task[i].name>>task[i].ddl>>task[i].expends;
int num=(1<<n)-1;//状态总数
for(int i=1;i<=num;i++) //比如 i=110 当前枚举到j=2 则 tmp=010 即从100转到状态110 只需要完成任务2即可
{
f[i]=INF;
for(int j=n-1;j>=0;j--)//枚举所有任务 因为如果取这个任务 我们会把这个任务放在当前状态i的最后完成 过先遍历字典序
//大的任务
{
int tmp=1<<j;
if(!(i&tmp)) continue;//如果当前状态i内没有task[j] 则不能转移到i
//i这个状态 最后完成的task是j
int ban=t[i-tmp]+task[j].expends-task[j].ddl; //i-tmp 表示上文中的100这个状态
if(ban<0) ban=0;
if(f[i]>f[i-tmp]+ban)//如果 更优 就转移
{
f[i]=f[i-tmp]+ban;
t[i]=t[i-tmp]+task[j].expends;
pre[i]=j;//pre[i] 表示到达状态i时 完成的最后一个作业的下标
}
}
}
cout<<f[num]<<endl;
output(num);
}
system("pause");
return 0;
}