博弈dp 以前做过差不多的 然后就写了 超内存了 自己写的是记忆化搜索 可以学一下大白书的67页例题28以及2013 ACM-ICPC吉林通化全国邀请赛play game
这题要写成递推的 然后降维 降维是网上学习的http://blog.csdn.net/hyogahyoga/article/details/8248881
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 5010;
int a[maxn];
int sum[maxn];
int dp[maxn];
/*int dfs(int l, int r)
{
if(l > r)
return 0;
if(dp[l][r])
return dp[l][r];
int& ans = dp[l][r];
ans = max(ans, sum[r] - sum[l-1] - dfs(l+1, r));
ans = max(ans, sum[r] - sum[l-1] - dfs(l, r-1));
return ans;
}*/
int main()
{
int n, m;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum[i] += sum[i-1] + a[i];
dp[i] = a[i];
}
for(int k = 2; k <= n; k++)
{
for(int i = 1; i+k-1 <= n; i++)
{
//dp[k][i] = max(sum[i+k-1] - sum[i-1] - dp[k-1][i+1], sum[i+k-1] - sum[i-1] - dp[k-1][i]);
dp[i] = max(sum[i+k-1] - sum[i-1] - dp[i+1], sum[i+k-1] - sum[i-1] - dp[i]);
}
}
printf("%d\n", dp[1]);//不是dp[n]
return 0;
}
广搜或者纯模拟
每次他都朝一个方向走 走不通才转弯
bfs进队列的时候加点判断一进队列就break 结构体多加个方向的参数
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 25;
char a[maxn][maxn];
int n, m;
int dir[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};
struct node
{
int x;
int y;
int dir;
};
bool bfs()
{
node s, e;
queue <node> q;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(a[i][j] == ‘Y‘)
{
s.x = i;
s.y = j;
s.dir = 0;
}
else if(a[i][j] == ‘D‘)
{
e.x = i;
e.y = j;
}
}
q.push(s);
a[s.x][s.y] = ‘@‘;
while(!q.empty())
{
node u = q.front();
q.pop();
if(u.x == e.x && u.y == e.y)
return true;
//printf("%d %d\n", u.x, u.y);
for(int i = 0; i < 4 ; i++)
{
int j = u.dir;
node v;
v.x = u.x + dir[j][0];
v.y = u.y + dir[j][1];
v.dir = u.dir;
if(v.x < 0 || v.x >= n || v.y < 0 || v.y >= m || a[v.x][v.y] == ‘#‘ || a[v.x][v.y] == ‘@‘)
{
u.dir = (u.dir+1) % 4;
continue;
}
a[v.x][v.y] = ‘@‘;
q.push(v);
break;
}
}
return false;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%s", a[i]);
if(bfs())
puts("YES");
else
puts("NO");
}
return 0;
}
这题开始时在第一棵树或者第二棵树下都行
开始以为是第一棵树 dp[][j] 表示第i分钟来回了j次最大值 因为我以为开始是1 所以j是奇数在第二棵树 偶数在第一棵树
di[i[j] = max(dp[i-1][j-1] + a[i][j%2], dp[i-1][j] + a[i][j%2])
开始在2也行所以我懒了在把这个复制了一次作为2开始的
有错请指出
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int dp[maxn][66];
int a[maxn][3];
int main()
{
int t, w, x;
while(scanf("%d %d", &t, &w) != EOF)
{
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= t; i++)
{
scanf("%d", &x);
a[i][x-1] = 1;
}
int m = 0;
for(int i = 1; i <= t; i++)
{
dp[i][0] = dp[i-1][0] + a[i][0];
m = max(m, dp[i][0]);
for(int j = 1; j <= w; j++)
{
dp[i][j] = max(dp[i-1][j-1] + a[i][j%2], dp[i-1][j] + a[i][j%2]);
m = max(m, dp[i][j]);
}
}
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= t; i++)
{
dp[i][0] = dp[i-1][0] + a[i][1];
m = max(m, dp[i][0]);
for(int j = 0; j < w; j++)
{
dp[i][j+1] = max(dp[i-1][j] + a[i][j%2], dp[i-1][j+1] + a[i][j%2]);
m = max(m, dp[i][j+1]);
}
}
printf("%d\n",m);
}
return 0;
}
和上次组队赛G题一样 裸的求无向图的割顶 我也只会简单的
大白书上有算法讲解
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 110;
vector <int> G[maxn];
bool iscnt[maxn];
int pre[maxn];
int low[maxn];
int cnt;
int dfs(int u, int fa)
{
int lowu = pre[u] = cnt++;
int child = 0;
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(!pre[v])
{
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if(lowv >= pre[u])
{
iscnt[u] = true;
}
}
else if(pre[v] < pre[u] && v != fa)
lowu = min(lowu, pre[v]);
}
if(fa < 0 && child == 1)//根有2个及以上子节点是割点
iscnt[u] = false;
low[u] = lowu;
return lowu;
}
int main()
{
int n;
int i, j;
int u, v;
char str[10000];
while(scanf("%d", &n) && n)
{
cnt = 1;
for(i = 1; i <= n; i++)
G[i].clear();
memset(pre, 0, sizeof(pre));
memset(low, 0, sizeof(low));
memset(iscnt, false, sizeof(iscnt));
while(gets(str) && str[0] != ‘0‘)
{
//puts(str);
char *p = strtok(str, " ");
int flag = 0;
while(p)
{
if(flag++)
{
v = atoi(p);
G[u].push_back(v);
G[v].push_back(u);
//printf("*%d\n",atoi(p));
}
else
{
u = atoi(p);
//printf("%d\n",u);
}
p = strtok(NULL, " ");
}
}
dfs(1,-1);
int sum = 0;
for(i = 1;i <= n; i++)
if(iscnt[i])
sum++;
printf("%d\n",sum);
}
return 0;
}
01背包
#include <cstdio>
#include <cstring>
using namespace std;
bool dp[50000];
int a[510];
int main()
{
int n,m;
dp[0] = true;
scanf("%d %d", &m, &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
for(int j = m; j >= a[i]; j--)
dp[j] |= dp[j - a[i]];
while(!dp[m])
m--;
printf("%d\n",m);
return 0;
}