博弈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;
}
简单递推一下就可以的 dp[i][j]代表第i个骰子是当前和为j有多少种 dp[i][j] += dp[i-1][k+s] s是当前骰子的值k是前面所以骰子的值的和 当前和就是k+s 最简单的dp
#include <cstdio>
#include <cstring>
const int maxn = 25;
__int64 a[maxn];
__int64 dp[1010];
__int64 pre[1010];
int main()
{
int n, x;
int i, j, k;
char str[100];
while(scanf("%d", &n) && n)
{
for(i = 0; i < n; i++)
{
scanf("%s", str);
__int64 sum = 0;
for(j = 1; str[j]; j++)
{
sum *= 10;
sum += str[j] - '0';
}
a[i] = sum;
//printf("%I64d\n", a[i]);
}
scanf("%d", &x);
memset(dp, 0, sizeof(dp));
for(i = 1; i <= a[0]; i++)
{
dp[i] = 1;
}
for(i = 1; i < n; i++)
{
//printf(" %d\n", a[i]);
memcpy(pre, dp, sizeof(dp));
memset(dp, 0, sizeof(dp));
for(j = 1; j <= a[i]; j++)
{
for(k = 1; k <= x; k++)
{
int sum = k + j;
if(sum > x)
continue;
dp[sum] += pre[k];
}
}
}
__int64 ans = 1;
for(i = 0; i < n; i++)
ans *= a[i];
//printf("%I64d %I64d\n", ans, dp[x]);
printf("%.5f\n", (double)dp[x] / ans);
}
return 0;
}
记忆化搜索
dp[i][j][k] 表示w = i h = j m = k最小值 开始初始化-1 不是-1就返回
题目求分成m部分 求最大值最小化
1.横向考虑 ans = min(ans, max(dfs(i, h, j), dfs(w-i, h, m-j))); 当前长度为w 宽度为h 分成m部分 那么枚举i j 当前状态dp[w][h][m]由dp[w-i][h][h-j]和dp[i][h][j]组成
2.纵向考虑 同上
给出出处 不是自己写的都给出参考的地方http://blog.sina.com.cn/s/blog_7189ea070100u3u2.html 自己还是菜鸟 做做水题差不多了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 22;
int dp[maxn][maxn][maxn];
int dfs(int w, int h, int m)
{
if(dp[w][h][m] != -1)
return dp[w][h][m];
if(m == 1)
{
dp[w][h][m] = w*h;
return w*h;
}
dp[w][h][m] = 999999999;
int& ans = dp[w][h][m];
for(int i = 1; i < w; i++)
{
for(int j = 1; j < m; j++)
{
ans = min(ans, max(dfs(i, h, j), dfs(w-i, h, m-j)));
}
}
for(int i = 1; i < h; i++)
{
for(int j = 1; j < m; j++)
{
ans = min(ans, max(dfs(w, i, j), dfs(w, h-i, m-j)));
}
}
return ans;
}
int main()
{
int w, h, m;
memset(dp, -1, sizeof(dp));
while(scanf("%d %d %d", &w, &h, &m) , w || h || m)
{
printf("%d\n", dfs(w, h, m));
}
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;
}
坑爹的模拟题 样例过了最后还是参考了百度 有一种情况没考虑到啊 以为是倒过来处理的 压缩出来如果是数字x 那么第x字符串可能还没有啊 我知道肯定听不明白
有机会画张图
#include <cstring>
#include <string>
#include <cstdio>
#include <iostream>
#include <map>
#include <cstdlib>
using namespace std;
char a[10000];
string mp[100000];
char s1[1000000];
int main()
{
int cas = 1;
string s2;
string str;
string str1;
string str2;
int n, i, j, l;
while(gets(s1))
{
int len = strlen(s1);
if(s1[0] == '0' && len == 1)
break;
s2 = "";
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%s", a);
mp[i] = a;
}
getchar();
int pre = 0;
for(j = 1, i = 0; j < n; j *= 10)
{
pre *= 10;
pre += s1[i++] - '0';
}
if(n == 1)
pre = s1[i++] - '0';
s2 += mp[pre];
for(; i < len;)
{
int m = 0;
for(j = 1; j <= n; j *= 10)
{
m *= 10;
m += s1[i++] - '0';
}
string ss = mp[pre];
if(m < n)
ss += mp[m][0];
else
ss += mp[pre][0];
mp[n++] = ss;
pre = m;
s2 += mp[m];
}
printf("Case %d: ",cas++);
cout << s2 << endl;
}
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;
}