2014台州学院ACM集训队寒假练习赛2

A Treasure Chest

博弈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;
}

C Game Dice

简单递推一下就可以的 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;
}

 

D Cake Cutting

记忆化搜索

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;
}

 

E An escape 

广搜或者纯模拟

每次他都朝一个方向走 走不通才转弯

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");elseputs("NO"); }return 0;
}

F Magic Tree

这题开始时在第一棵树或者第二棵树下都行

开始以为是第一棵树 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;
}

H Decompressing in a GIF

坑爹的模拟题 样例过了最后还是参考了百度 有一种情况没考虑到啊 以为是倒过来处理的 压缩出来如果是数字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];elsess += mp[pre][0];mp[n++] = ss;pre = m;s2 += mp[m];}printf("Case %d: ",cas++);cout << s2 << endl;}return 0;
}

 

I Network

和上次组队赛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;
}

J Bessie's Weight Problem

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;
}