tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

2012 noip复习(含tyvj、usaco)


2012-11-5:noip 马上要到了! 从头开始复习自己的题目: P1000、P1001、P1002、p1006:模拟,小心一些 P1007:贪心(排座位,找最优的位置分排)

P1004:记忆化的 DP,策略是 1.该方向有点可去(在图内);2.该点高度低;3.该点的步数+1 大于本点(贪心)
//若本点已有记录了,直接返回该值即可


P1005:标准的 01 背包 P1008:传球游戏(这个需要考虑出状态了,f[i][j]为穿到第 i 次时,第 j 个人时的传球方式总数,转 移是 f[i][j]=f[i-1][find(j-1)]+f[i-1][find(j+1)] 要考虑一下这是个环) P1011:双线程 DP 就是有两各位置都有决策,判断横纵边界,四种走法都是策略,不能走到一起就代 表每一个人只传一次(用状态和状态转移去表示条件) P1012:火柴棒等式(需要一个常量表,然后 for 循环枚举即可) P1013:找 GF(类似于 01 背包,但是 2 维的,即有两种费用) P1014:乘法游戏。在每一个移动中,玩家拿出一张牌,得分是用它的数字乘以它左边和右边的数,所以不允许拿第 1 张和最后 1 张牌。 (划分 DP:循环区间长度[最小为 3],循环起点位置,终点位置) for(int i=0;i<n-2;i++) {dp[i][i+2]=da[i]*da[i+1]*da[i+2];} //先进行一次预处理 for(int i=3;i<n;i++) //区间长度循环(最短长度为三) for(int j=0;j<n-i;j++) //左起点循环 for(int k=j+1;k<j+i;k++) //k 代表最后一个数 { dp[j][j+i]=max(dp[j][j+i],dp[j][k]+dp[k][j+i]+da[k]*da[j]*da[j+i];) } P1015:公路乘车(NP 背包,for(i->n) for(int j=0->v)) P1016:01 背包的简单变形,找最小可达到的剩余空间。 P1017:冗余关系(普通的并查集:不断更新,不断缩短路径,不断判断共树) P1018:阶乘统计,就是一个模拟啦,高精度计算方法 P1019:配对,只需要快排一下,然后贪心即可。 P1020:寻找一系列数中质因数最大的数字(正常去做,也可以筛法找质数,再去比较) P1021:线段长度(数论数值)就是快排一下,让后一点点推最大的线段长度 P1022:进制转换,转换成一个负进制(其实就是分成正负两种去讨论,取模进位,和正常的一样!) P1023:奶牛的锻炼(这道题真是让人伤心的一道动态规划,自己写的就是不对,一下是网上的版本, 不过他的状态设定,和状态转移确实比我的更加简洁一些!!他最值得借鉴的地方就是说,直接将休 息的值付给了 f[i][0]=max(?,f[i-j][j]);避免了对后面 f[i-j][j]的休息决策转移) for(int i=1;i<=n;i++) //n 分钟 for(int j=1;j<=m;j++) //m 的疲惫值 { f[i][j]=max(f[i-1][j-1]+a[i],f[i][j]); //让这个点和以前再走一步的值比较 if(i>=j) f[i][0]=max(f[i][0],f[i-j][j]); //处理一下这里的休息值,和产生这么多的疲劳值的位置,留下更大的。 f[i][0]=max(f[i][0],f[i-1][0]); //在这里的再比较一次 } printf("%d\n",f[n][0]); P1030:这是一个图搜索题,分为四个方向,dfs、bfs 均可,注意对于输入数据的处理 两种输入有所不同{scanf(?)在一行结束之后要 getchar 到下一行,而 cin 则不需要换行} P1031:热浪(spfa 的最短路,存边使用前向星 a[i],b[i],c[i]) P1034:尼克的任务()
for(i = n; i >= 1; --i) { while(j >= 1 && p[j] >= i) //有任务,并且任务可做(在时间段内 { if(p[j] == i && max[i + t[j]] > max[i]) { max[i] = max[i + t[j]];} //倒序循环时间 ,看该时间段的情况去决策,结果在 max[1]内存储。

--j; }

//只有找到一个能够休息更多的任务才会覆盖原来的状态

if(p[j + 1] != i)//最后再计算一下,看看最优的任务结束之后可不可以再获得一个休息 { max[i] = max[i+1] + 1; } }

P1035:棋盘覆盖(基础的匈牙利匹配,当前的点是一个图,与他相连的可去点为另外一个图,二分图 匹配) P1037:阶乘统计 2(和 1 差不了太多,模拟题嘛,都是差不多的,有耐心,要细心) P1040:表达式计算一(这个模拟稍稍恶心一些,读入 string 类型的,然后把运算符和数字分离出来) P1042:表达式计算三(二我没做[只不过用一下高精度,多了一个减法],这个三就比较高级了,把运算 符和数字分离出来之后,我还考虑了半天,后来发现这用栈的思想是再好不过的了,运算符优先级高 的进栈,不够高的话,先把栈里的计算完) -?>不过话说更恶心的表达式计算四我没有做,一时没想好怎么去算“ “) (” ”它们的优先级,二 是没明白什么叫括号可能不完整。 P1044:这应当是动态规划的起步题目了,最基础的一个。但是这个还是很有启发性的,就是说你是把 数据往下存,还是接受以前算过的最优子! !
dt[i][j]=dt[i][j]+max(dt[i-1][j],dt[i-1][j-1]);

P1047:乘法游戏。这是最近做的一道动归题目,相对而言思想更广泛,更实用,划分 DP,枚举追寻 以前的最优子。
for(int i=1;i<=n;i++) //注意我们常常用一个这样的方法预处理一下 for(int j=i;j<=n;j++) { sums[i][j]=sums[i][j-1]*10+nums[j]; } for (int i=1;i<=n;i++) { //划分区间的 dp,经典!(注意初始值,以及划分子区间时的要求)

f[i][0]=sums[1][i]; for (int j=1;j<=k&&j<i;j++) for (int h=1;h<=i-1;h++) { if (f[i][j]<f[h][j-1]*sums[h+1][i]) {f[i][j]=f[h][j-1]*sums[h+1][i];} }

}

cout<<f[n][k]<<endl;

P1048:田忌赛马(嗯,这道题坑了我好几次,不是贪心,而是动归) ,具体的决策并非排序后就可以贪 心了,因为每一次但你发现有相等的,赢得,甚至是输的,他都可以变成去消耗齐王最猛的马而为后 面的马争取机会,但是究竟牺牲几个,牺牲谁,这是一个必须要动归的事情。
for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (a[i]>b[j]) g[i][j]=200; if (a[i]<b[j]) g[i][j]=-200; if (a[i]==b[j]) g[i][j]=0; } //这个先快排一次,此处略去,这个预处理非常实用,直接减小了后面转移时 coding 的难度

for (i=1;i<=n;i++) for (j=0;j<=i;j++) f[i][j]=-100000; f[0][0]=0; for (i=1;i<=n;i++) for (j=0;j<=i;j++) { if ((j>0)&&(f[i][j]<f[i-1][j-1]+g[j][i])) f[i][j]=f[i-1][j-1]+g[j][i]; if ((n-(i-j)+1>=0)&&(j<=i-1)&&(f[i][j]<f[i-1][j]+g[n-(i-j)+1][i])) f[i][j]=f[i-1][j]+g[n-(i-j)+1][i]; }ans=0; //以上的这两行嘛,非常好,正确的表示出三种转移,胜负平!而每一个转移都恰好使用重叠子! //枚举田忌马匹数量 //枚举齐王的马

for (i=0;i<=n;i++) if (f[n][i]>ans) ans=f[n][i];

P1049:最长不下降子序列(很有意义的一道)
opt[1]=1; for (int i=2;i<=n;i++) { opt[i]=1; for (int j=1;j<i;j++) { if(a[i]>=a[j]&&opt[i]<opt[j]+1) opt[i]=opt[j]+1; } } for(int i=1;i<=n;i++) if(ans<=opt[i]) ans=opt[i]; //划分 dP,去查找以前的所有的值,继承最大的一个。 //初始值

P1050:最长公共子序列(这道动归我看了好多次,总是容易忘记,唉…[注意它求的不是连续公串])
for (i=1;i<=s1.length();i++) for (j=1;j<=s2.length();j++) { if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } //相等的可以继承以前,并且更新 //不等的话只需要继承,这样最大值可以向后传递 //相当于把两个字符串的各个位置都比较了一次

P1051:选课(树形 DP 起步题,当然更基础的以后会说,这里强调树形结构的多叉转二叉) 一般来讲,如果子物品还有子物品,那么就不能用有依赖的背包去写了。
void dfs(int x) { for (int i=1;i<=m;i++) f[x][i]=w[x]; for (int i=1;i<=a[x][0];i++) { int t=a[x][i]; dfs(t); for (int i=m;i>0;i--) for (int j=0;j<i;j++) { f[x][i]=max(f[x][i],f[t][j]+f[x][i-j]); } } } //结果在 f[0][m]中找 //本题中的 a 数组存储的是 x 的第 i 个子物品 //子调用去讨论子物品(先计算重叠子结构) //x 节点的子节点(重叠子结构)已经计算完了,选 i 件(相当于体积)进行 01 背包 //记录下给 x 节点各种“体积”时的价值(只有一个物品) //传递节点

????????注意这样的存储方式,个人认为还不错哦 a[x][++a[x][0]]=i; {由 x 到 i 指向} P1055:合并沙子,这道题目是很好的区间 dP,基础题,只要找到长度,以及边界就好办了。
for(int i=1;i<=n;i++) for(int k=2;k<=n;k++) for(int i=1;i<=n;i++) { if((i+k-1)>n) {break;} int j=i+k-1; for(int p=i;p<=j;p++) { f[i][j]=min(f[i][j],f[i][p]+f[p+1][j]+nums[i][j]); } } for(int j=i+1;j<=n;j++) {nums[i][j]=nums[i][j-1]+saves[j];}

P1057:金明的预算方案,由于题目较弱,不用区间 DP 也可以,详见背包九讲中的有依赖的背包。 完整标程如下:
#include <iostream> #include <cmath> #include <cstring> using namespace std; struct node { int v; int p; int q; }data[61]; int f[60][32001]; int n, m; int ans[32001]; int main() { //freopen("1.txt", "r", stdin); while(cin >> n >> m) { memset(f, -1, sizeof(f)); f[0][0] = 0; n /= 10; for(int i = 1; i <= m; i++) { cin >> data[i].v >> data[i].p >> data[i].q; data[i].v /= 10; f[i][0] = 0; } //对附件集合进行一次 01 背包,存储到他的父节点里 for(int i = 1; i <= m; i++) { if(data[i].q == 0) continue; for(int j = n; j >= data[i].v; j--) { if(f[data[i].q][j - data[i].v] != -1) { f[data[i].q][j] = max(f[data[i].q][j], f[data[i].q][j - data[i].v] + data[i].v * data[i].p); } } } //对价值进行处理,更新为各物品组主件+附件,对各个父节点操作 for(int i = 1; i <= m; i++) { if(data[i].q != 0) continue; for(int j = n; j >= 0; j--) { if(f[i][j] != -1) { if(j + data[i].v > n) f[i][j] = -1; else { f[i][j + data[i].v] = max(f[i][j + data[i].v], f[i][j] + data[i].v * data[i].p); f[i][j] = -1; } } } } //变成有物品组的背包问题,对各个父节点进行 0,1 背包 memset(ans, -1, sizeof(ans)); //物品组 //价格 //重要度 //所属主件的编号 //网上的 AC 版本,将树形 dp 用有依赖的背包解决了。

ans[0] = 0; int _max = 0; for(int i = 1; i <= m; i++) { if(data[i].q != 0) continue; for(int j = n; j >= data[i].v; j--) { for(int k = j; k >= data[i].v; k--) { if(f[i][k] != -1 && ans[j - k] != -1) { ans[j] = max(ans[j], f[i][k] + ans[j - k]); _max = max(_max, ans[j]); } } } } cout << _max * 10 << endl; } return 0; }

P1059:过河呦!青蛙很讨厌踩到石子,但是看来是无法避免一些了,我们要计算出最小的数量(这道 题的状态和转移方程都很好想,但是数据明显太大,数组是开不下的,于是我们需要状态压缩!这道 题的特殊之处在于,如果石头之间的距离大于 100 那么中间的就可以减少一些了) {本题难的不是 DP 方程,而是难在了压缩路径上面,首先,DP 方程是很好想出的,每次跳的范围只能在[S,T]之间,所以到某一个位置时,只要从前面的[S,T]这个位置找一个最小值转移过来就行了,在
判断一下这个点有没有石子,有就+1,否则直接转移。 但是一看数据范围,10^9,好吧,裸方法可以去使了…… 仔细观察题目数据不难看出虽然总长度是 10^9,但是石子最多却只有 100 个,这说明了什么?说明在这条路上石子出现是很稀疏的,这就可以用到了压缩路径的办法。 经过一系列的数学证明可以得出,当两个石子之间的距离大于 100 之后,两个石子之间的空隙跟空隙为 100 的最优值没有差别(因为 S 和 T 的范围也很小),这样就把一个极大的空隙变成了一个在 100 以内的空隙。也就是相当于我们把独木桥变短了。

} P1061:这道题一开始我真没想到状态,题解很好,还附带了状态压缩 haha 关键的建模:f[i][x1][x2][x3]表示在第 i 时刻三人位置的状态,但其实我们会发现,必定有一个在 p[i] 的位置上,就是要求的位置,因此这 3 个中有一个多余,可以变成 f[i][x1][x2],但是依然爆,这是我 们就需要滚动数组了(最后的优化方法) ,决策只有三种,分别让三个人去。
最后还有一种情况就是 S=T 时,这时每次能跳的情况只有一种,就从起点累计一遍,mod S=0 就把 ans+1,输出 ans。 if (f[(k+1)&1][i][la]>f[k&1][i][j]+map[j][a]) f[(k+1)&1][i][la]=f[k&1][i][j]+map[j][a]; if (f[(k+1)&1][la][j]>f[k&1][i][j]+map[i][a]) f[(k+1)&1][la][j]=f[k&1][i][j]+map[i][a]; if (f[(k+1)&1][i][j]>f[k&1][i][j]+map[la][a]) f[(k+1)&1][i][j]=f[k&1][i][j]+map[la][a];

P1070:罗马数字(模拟题,其实罗马数字的书写是有规律的…只有且必有比某一字母大时它会出现) P1073:加分二叉树(树形 DP 贼基础的题目,顺便温习一下前、中、后序遍历)
int dp(int l,int r) { int i,j,ans,now; if (f[l][r]) return f[l][r]; if (l>r) return 1; ans=-0x7fffffff; for (i=l;i<=r;i++) { now=dp(l,i-1)*dp(i+1,r)+a[i]; if (now>ans) //划分不同区间去枚举子树的根节点(这里有可能 l>i-1...)更新出最优解 //这里返回的都是 l >= r 的不可能值 //到达底层返回 1 //树形 dp,从叶到根,枚举根的情况。

{ ans=now; g[l][r]=i; } } f[l][r]=ans; return ans; }

//修改为更优的根

//另外开了一个数组去存储这个区间上的最优根节点,以后输出所用

//记录这个区间上的大小 //返回给上一层

P1076:数字三角形二(这道题要求结果 mod100 最大,这意味着转移方程要发生变化了!但其实也没什 么的哈!只需要中间每一步都加上 mod100 取最大的重叠子就可以了) P1077:有理逼近(这道题,我只用了枚举的方法,再加上一个简单的数学优化!ok) P1079:数字三角形三(题目要求在经过某些特定点的时候,求最后的最大值,其实你只需要把和这个 点相对立的点,就是不可以走的点赋值成-0x7fffffff 就可以了!) P1080:N 皇后问题(非常经典的一个问题,考察了你的数学头脑,那就是说每一个位置的坐标都可以对 应着一个横纵斜线的方程[相当于数学中的[y=x+?或,y=-x+?])
void dfs(long dep) { if(dep>n) { cnt++; if(cnt>3) return; for(long i=1;i<=n;i++) { if(i!=1) cout<<" "; cout<<ans[i]; } cout<<endl; return; } for(long i=1;i<=n;i++) if(!lie[i]&&!dui1[f1(dep,i)]&&!dui2[f2(dep,i)]) { lie[i]=dui1[f1(dep,i)]=dui2[f2(dep,i)]=true; ans[dep]=i; dfs(dep+1); lie[i]=dui1[f1(dep,i)]=dui2[f2(dep,i)]=false; } }

P1088:treat 其实我一直不喜欢做英文名字的题目,但这个看上去还不错,(本以为很简单,但是自 己写的却失败了,唉?)
f[1][1]=a[1]; f[1][0]=a[n]; for (i=2;i<=n;i++) for (j=0;j<=i;j++) { //对应着两种决策,取走或不取走。 if ((j>0)&&(f[i-1][j-1])&&(f[i][j]<f[i-1][j-1]+a[j]*i)) f[i][j]=f[i-1][j-1]+a[j]*i; if ((j<i)&&f[i-1][j]&&f[i][j]<f[i-1][j]+a[n-(i-j-1)]*i) f[i][j]=f[i-1][j]+a[n-(i-j-1)]*i; } //这个数组的状态很好玩啊, f[i][j] 表示前 i 个取走了 j 个的最大值

for(int i=1;i<=n;i++)

if(f[n][i]>maxn) {maxn=f[n][i];}

P1096:其实就是一个 01 背包,每一个状态里面都是达到这个数的可能情况数量。 P1098:任务安排(这道题我的代码失败了,最后看一看题解吧,思想是一样的,但是我却失败了,看 来有很多的细节,优化,是动规精髓所在)
for(int i=1;i<=n;i++) { cin>>ti[i]>>ki[i]; tsums[i]=tsums[i-1]+ti[i]; ksums[i]=ksums[i-1]+ki[i]; } memset(f,100,sizeof(f)); f[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<=i-1;j++) { //前面的分组结果 f[j],这里又多分一组,为了避免以后不知道时间,直接将后面所有的都乘一次,以后 s 在增加时再乘 f[i]=min(f[i],f[j]+(tsums[i]-tsums[j]+s)*(ksums[n]-ksums[j]));//这里的状态转移其实只是存下同类中的最优解,不断更新。 } cout<<f[n]<<endl; //非常实用预处理

P1109:N 阶幻方,数论数值,计算式子:n=(n*(n*n+1))/2; P1112:舞会 2(开一个二维数组,贪心一下就可以了!哈^_^哈!) P1113:魔族密码(很水的一个动规,类似于最长不**子序列,只不过判断条件是是否为前缀)
if((a.length())>(b.length())) {return false;} for(int i=0;i<a.length();i++) { if(a[i]!=b[i]) {return false;} } return true;

P1114:搭建双塔(其实这道题我一开始认为它是和双线程 DP 有一样的思路(其实不是双线程啦),这 样的方法也确实成功了,但是你要注意一下,循环的区间大小,大于了里面实际可以转移的部分,在 内部要判断一下)
f[0][0]=1; for(int i=1;i<=n;i++) for(int p=sums/2;p>=0;p--) for(int t=sums/2;t>=0;t--) { //把第 i 个块分别放在左边或右边 if(f[p-hi[i]][t]==1&&(p-hi[i])>=0) if(f[p][t-hi[i]]==1&&(t-hi[i])>=0) } f[p][t]=1; f[p][t]=1;

P1116:被 7 整除,数论数值的题一般都有一个公式,这道题你会发现那些数是有规律的,循环出现。 P1120:靶形数独,哈哈,这道题么,其实只是一个搜索,但是剪枝要注意,最好是让顶层的枝杈尽量 小,因此我们要优先去枚举已知数最多的一个区域内的各种情况。 P1122:最优贸易(这个集合了最短路的模拟,搜索;却只需要由 1?n 再由 n?1 用两次 spfa,分别求 出到第 i 个点的最大卖价,最小买价[并非是第 i 点的,而是由 1?n 或 n?1 路径上得到的最优值], 两次 spfa 能保证第 i 点可以从 1 到达,并且再走到 n)以下附带前向星,qs,以及 spfa 标程。
void qs(int l,int r) { int i,j,mid,t; i=l; j=r;

mid=a[(i+j)/2]; while(i<=j) { while(a[j]>mid) j--; while(a[i]<mid) i++; if(i<=j) { t=a[i];a[i]=a[j];a[j]=t; t=b[i];b[i]=b[j];b[j]=t; t=c[i];c[i]=c[j];c[j]=t; i++;j--; } } if(i<r) qs(i,r); if(j>l) qs(l,j); } void spfa(int v0) { int h,t,now,next; h=1;t=2; dist[v0]=0; que[h]=v0; vi[v0]=true; while(h!=t) { now=que[h]; for(int i=path[now];i<=path[now+1]-1;i++) { next=b[i]; if(dist[now]+c[i]<dist[next]) { dist[next]=dist[now]+c[i]; if(!vi[next]) { vi[next]=true; que[t]=next; t++;if(t>100) t=1; } } } vi[now]=false; h++;if(h>100) h=1; } }

P1124:花店橱窗 (这道题的 DP 状态及方程比较好想出来, 但是边界问题我处理了半天也没整明白, 唉?)
for(i = 1; i <= n; i++) for(j = i; j <= m - n + i; j++) f[i][j] = -100000000; for(k = i - 1; k < j; k++) { //最后我才发现在这里赋初值比较合理一些,因为这样不会把后面的提前变小,不然会彪掉….

if(f[i - 1][k] + map[i][j] > f[i][j]) { f[i][j] = f[i - 1][k] + map[i][j]; p[i][j] = k; } } //存储一下这个区间上的最优解,以后要求输出方案是什么样的。

P1165:科学计数法,一道非常非常非常非常非常非常非常非常恶心的字符串处理,竟然需要一位一位 的用高精度方式去处理,唉?? P1171:自然数拆分,中午刚用欣然的程序过的,DP 方程非常简洁
for(int i=1;i<=n;i++) {w[i]=i;} memset(f,0,sizeof(f)); f[0]=1; for(int i=1;i<=n;i++) for(int j=w[i];j<=n;j++) cout<<f[n]-1<<endl; //看这里,把 j 变成了以前已经拆过的一个数,利用了重叠子 {f[j]+=f[j-w[i]];} //但是题里不允许自己分成自己,所以要减去 1 //最开始每一个数都可以分成自己和 0

P1195:最后的晚餐(网上的 AC,和自己的差一些,自己写的维数多了一个(不必要的状态),而且只 需要与前一分钟的比较,我的转移也有错误。)
f[1][0]=a[1]+c[1];f[1][1]=b[1]; for(i=2;i<=n;i++) { f[i][0]=min(f[i-1][0]+a[i],f[i-1][1]+a[i]+c[i]); f[i][1]=min(f[i-1][1]+b[i],f[i-1][0]+b[i]+c[i]); } min(f[n][0],f[n][1])); //转移的实质,只需要和前一分钟比较并继承

P1199: 邮票问题 (一开始还以为这题很难, 没有办法去做,但其实这只是一个比较 dp,在继承的时候, 只需要判断能否取到[而且所用总数没有超过 n])
for(i=1;i<=m;i++) for(j=w[i];j<=Maxi+w[i];j++) if((f[j-w[i]])&&(p[j-w[i]]+1<=n)) { if(f[j]) p[j]=min(p[j],p[j-w[i]]+1); else { f[j]=true; p[j]=p[j-w[i]]+1; } } //如果本位已经可以取到了,看看能否将粘贴个数优化一下。 //粘贴他之前的已经可以取到了,而且粘上去没有超过 n

P1209:拦截导弹,一个最长不下降,一个最长不上升,各求一次。
s[1]=1; for(int i=2;i<=n;++i) { s[i]=1; for(int j=1;j<i;++j) if(a[i]>a[j]&&s[i]<s[j]+1) s[i]=s[j]+1; } for(int i=2;i<=n;++i) { x[i]=1; for(int j=1;j<i;++j)

if(a[i]<=a[j]&&x[i]<x[j]+1) x[i]=x[j]+1; }

//注意这里和刚才是恰反的。

P1212:积木游戏(NOI97)一看这题就觉得太有分量了,转移方程是看的题解,看完之后发现其实也 没什么哈,不过他巧妙的把题中要求编号排放顺序的要求变成了 DP 的转移顺序,从而不需要考虑什么 小号大号,也就是说,有序的转移往往可以达到题中一些条件。
int n,m,x[101],y[101],z[101]; int f[101][101][4]={0}; //积木数,摞数,三边长度 //转移的主数组 //以下这三个函数是用来,在不同的放置方式时返回的长宽高 int h(int p,int k) { if(k==1) {return x[p];} if(k==2) {return y[p];} if(k==3) {return z[p];} } int check(int fx,int fj,int fb,int fs,int fk) { if((doitx(fx,fb)>=doitx(fs,fk))&&(doity(fx,fb)>=doity(fs,fk))) {return f[fx][fj][fb];} if((doitx(fx,fb)>=doity(fs,fk))&&(doity(fx,fb)>=doitx(fs,fk))) {return f[fx][fj][fb];} return 0; } void dp() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int a=0;a<=i-1;a++) for(int q=1;q<=3;q++) for(int b=1;b<=3;b++) //把以前可以的继承过来 //这五层循环真是我写的 DP 中最疯狂的了 } int doitx(int l,int r) { if(r==1) {return y[l];} if(r==2) {return z[l];} if(r==3) {return x[l];} } int doity(int ll,int rr) { if(rr==1) {return z[ll];} if(rr==2) {return x[ll];} if(rr==3) {return y[ll];}

//下面的盒子,第 j 堆,下面盒子的放法,上面的盒子,上面的放法(这个函数用来检测这么放是否合乎关于边长的大小要求)

[i][j][q]=max(f[i][j][q],max(check(a,j,b,i,q),f[a][j-1][b])+h(i,q));//注意不要覆盖原赋值 } int main() { for(int i=0;i<=n;i++) f[0][0][1]=0; 输入数据 dp(); for (int i=1;i<=n;i++) cout<<mx<<endl; return 0; } for (int j=1;j<=m;j++) for (int k=1;k<=3;k++) mx=max(mx,f[i][j][k]); for(int j=0;j<=m;j++) for(int k=0;k<=3;k++) f[i][j][k]=-0x7fffffff;

P1214:硬币问题(感觉上就是背包哈,但是要存的是达到这个体积,最少和最大各要用多少个钢镚) P1233:数列(其实这道题最好用二维数组表示状态,很好理解二维的 f[i][j]表示前 i 个数中去掉 j 个能得到的最优解,但是下面有一个一维数组的,未看懂)
init(); //初始值 f[i]=1; for(i=2;i<=n;i++) { for(j=1;j<=i-1;j++) //继承之前的所有子 f[i]=max(f[i],f[j]+1); //更优的条件是这个区间 //在第 i 个数的位置

if((a[i]<=i)&&(a[j]<=j)&&(a[i]-a[j]>0)&&(a[i]-a[j]<=i-j)) if(a[i]<=i)

ans=max(ans,f[i]); }

P1245:取数游戏(这是一个贪心的题目,快排一下,让后每一次取出最小的就行了) P1246:乌龟在跳的数字格子
int n,p,m; bool a[101][10001]={0}; 这是一种类似背包想法的存储方式:a[i][j]表示第 i 个格子处能否取到 j(bool 类型的嘛) int boxs[101]={0}; cin>>n>>p>>m; for(int i=1;i<=n;i++) { cin>>boxs[i]; } a[1][0]=1; for(int i=1;i<=n;i++) for(int k=1;k<=p;k++) for(int j=0;j<m;j++) { if((i-k)>0&&a[i-k][j]) { a[i][(((boxs[i]%m)*k)%m+j)%m]=true; } } for(int i=m;i>0;i--) if(a[n][i]==true) cout<<i; return 0; //继承过来以前的值 //格子数,步数,模

P1267:Way selection(就是一道匹配题哈)在进行匈牙利匹配之前,先计算出每一个点可以匹配的 所有位置,然后再去增广!
判断:if(t*t*v*v>=((ax[j]-x)*(ax[j]-x)+(ay[j]-y)*(ay[j]-y))) data[i][j]=true; for(int i=1;i<=r;++i) { memset(state,0,sizeof(state)); if(find(i)) ans++; } bool find(int k) { for(int i=1;i<=a;++i) { if(data[k][i]&&!state[i]) { state[i]=true; if(result[i]==0||find(result[i])) { result[i]=k; return true; } } } return false; }

P1274:小说发表(自己写的很接近了,但是你还是没有想好转移方程,转的麻烦了!,其实很多的不 需要划分 dp,可以只与前一个有关)
int n,t,m,nums[21]={0},f[21][21][21]={0}; cin>>n>>t>>m; for(int i=1;i<=n;i++) { cin>>nums[i]; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<=t;k++) //各种决策为:在本刊上多加一个,在本刊上不加,在前一刊上加,继承以前的。 if(k>=nums[i]) {f[i][j][k]=max(f[i-1][j][k-nums[i]]+1,f[i-1][j][k]);} else if(j>0) {f[i][j][k]=max(f[i-1][j-1][t-nums[i]]+1,f[i-1][j][k]);} cout<<f[n][m][t]<<endl;

P1275:刷钱(话说这道题我根本没有注意到竟然可以用 01 背包去做,以后一定要注意!!)其实很多题就是这样,稍稍变一变,就是一个非常成 熟的动规,只不过可能多了几个条件需要判断罢了。 P1287:魔塔防御,这道 DP 的题目是看的题解,关键的思想是用贪心法为动规创造条件,你会发现其 实红法师不用考虑,因为他们的攻击无后效性
for(i=0;i<=n;i++) for(j=0;j<=n-i;j++) { if((i==0)||(j==0)) { if((i==0)&&(j==0)) if((i==0)&&(j!=0)) if((i!=0)&&(j==0)) } else f[i][j]=Max(f[i-1][j]+((i-1)*b+t)*j*g,f[i][j-1]+(i*b+t)*(j-1)*g); //两种状态转移 (继承来的,是放一个蓝,还是一个红)?其实就是平衡一下蓝红法师的数量啊 ans=Max(ans,f[i][j]+(n-(i+j))*(i*b+t)*(g*j+r)); } f[i][j]=0; f[0][j]=f[0][j-1]+t*(j-1)*g; f[i][0]=0; //三个特殊的状态转移,边界的处理 //n 个中安排 i 个蓝法师 //其余的安排绿法师

P1305:最大子序和(用到了单调队列去优化,这个可以不用掌握,但既然写过一个,就看看吧) 做动态规划时常常会见到形如这样的转移方程:

f[x] = f[x-?]+ min/max{g(k) | b[x] <= k < x} + w[x] 但是这个搜索 b[x]却是一个非常浪费时间,空间的事情,而我们只需要知道之前的一个最值, 那我们就可以在每一次过程中去维护一个最值,这样就大大的节省了时间。
#include<stdio.h> #include<iostream> using namespace std; int n,m,nums[300001]={0},s[300001]={0},que[300001]={0},rec[300001]={0}; int h=1,t=1,ifs=t,maxn=-0x7ffffff; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>nums[i]; }

que[1]=0; s[0]=0; for(int i=1;i<=n;i++) { s[i]=s[i-1]+nums[i]; rec[i]=s[i]-s[que[h]]; ifs=t+1; while(s[i]<s[que[t]]&&t>=1) { t--; } t=t+1; que[t]=i; if(ifs!=t) { if(h<t) { if(que[h]<(i+1)-m) {h+=1;} } else h=t; } else { if(que[h]<(i+1)-m) {h+=1;} } } for(int i=1;i<=n;i++) { if(rec[i]>maxn) { maxn=rec[i]; } } cout<<maxn<<endl; return 0; } //该数组用来存储的是 //记录下现在的队头。 //更新现在的单调队列,边计算,边更新 指针留下 覆盖掉不好的 //知道找到一个更优的,把之后的都去掉,我们只要一个最优值 //还是我们常说的预处理哈 //que[h]记录的是在 i 之前的最高解

P1315:经营餐厅(其实就是一个贪心哈,每一次选最小的,再排序,再选??) P1326:剑人合一(这个最短路哈,只需要前向星就可以了,注意我们要用以下的程序存下以 i 为头的 边的最初位置[在前向星中的位置])
for(int i=1;i<=m;i++) if(path[x[i]]==0) path[x[i]]=i; path[n+1]=m+1; for(int i=n;i>=1;i--) if(path[i]==0) path[i]=path[i+1]; //用 path 去记录每一个点边的起始位置,如果没有的话,直接赋成以前的(否则下面的 spfa 就不好进行了)

P1336:火车进栈(他就是一个栈式使用,每一次枚举各位置,再去检验这个全排列是否能通过进栈的 方法转换过去!)
while (ap<=n) { //每一次比较都是:栈顶数,剩余数,和当前需要匹配的数,相等,匹配下一个,否则进栈 //如果没有剩余的数了,而所需匹配的数!=栈顶元素,那么这个全排列是不可能的 if(bp>n&&a[ap]!=s.top()) break; if(a[ap]!=bp&&(s.empty()||a[ap]!=s.top())) {s.push(bp);bp++;}

if(a[ap]==bp) {ap++;bp++;} if(!s.empty()&&a[ap]==s.top()){ap++;s.pop();} } if(ap>=n) {for(int i=1;i<=n;i++) cout<<a[i];cout<<endl;a[0]++;}

P1348:清理内奸(第一个问是匈牙利匹配,第二个问是贪心:首先快排一下所有忠臣的等级数,但是 我们一定要记录下所有忠诚的攻击范围) P1361:子串清楚(这道题我希望你能体会到什么时候去使用栈),题解上的思想就是不断把主串入栈, 并且一直判断栈顶元素是否和负串最后一个元素相同,如果一样,则匹配一次,可以用 KMP 优化,但 是也没关系,如果匹配成功了,那么栈顶的这些元素统一出栈,再继续下去,知道最后一个。 P1423:GF 和猫咪的玩具:floyd 的最短路就可以了
for(int k=1;k<=n;k++) for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) { if(dis[i][j]>dis[i][k]+dis[k][j]) { dis[j][i]=dis[i][j]=dis[i][k]+dis[k][j]; } }

P1472: 过河 (这道题又是用贪心的想法为动态规划创造可能, 首先慢的人过河时间肯定不会再减小了, 我们只希望送船回来的人速度能够快一些,所以唯一有可能应用的两个人,就是先要快排,然后用最 快的前两个人[至于为什么是前两个,而非一直用最快的一个,那是因为如果让最快的两个人过去,再 由第二快的人送船回来,与最慢的过去,最快的回来送船,这样有可能快一些]所以说规划是必须的, 决策只有两种)
qs(1,n); f[1]=nums[1];f[2]=nums[2]; for(int i=3;i<=n;i++) { //这倒规划的亮点啊!两种策略,不要小看(一定要保证每一次转移之后吧,船还在东岸,如果在西岸就不对了) f[i]=min(f[i-1]+nums[1]+nums[i],f[i-2]+nums[i]+nums[1]+nums[2]*2); } //好好想一下吧 //边界问题一定要注意!(最初的几个值一般要特殊的给出)

//保证回来的时间最短(因为去的时间是不可能减小的),保证每一次转移后船都在此岸

cout<<f[n]<<endl;

P1524:合并方程式(还不错的一个字符串处理题,注意存储着字符的数组,可以直接当做一个数字来 传递。eg:s[i]=’a’; ? nums[s[i]]??nums[97]; 另外吧,string 类型读入的时候,第 一个数据是从 s[0]开始的。) P1570:买花砍价,本应是一道非常水的题,但是我竟然失败了。这种设计到方案数量的题嘛,一定要 记住这种形式:f[i]=f[i+x[?]]+f[i+x[?]]+?;(就是说有多个情况转移而来!) P1745:连通验证(这道题猥琐的原因是:点较多,而且询问太多。因此我们决定用 bool 存储各点之 间的信息,离线算法,计算好了,直接输出结果;此题的另外一个重点是使用了数组去模拟链表,详 见标程)
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> using namespace std; bool p[8001][8001],h[8001],f[8001]; int list[8001],next[16001],b[16001],q[8001]; int n,m,q1,i,j; void init() { //数组模拟链表存储,BFS 判断是否联通。

int u,v,tot=0; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); tot++; b[tot]=v; next[tot]=list[u]; list[u]=tot; } memset(p,false,sizeof(p)); } void bfs(int s) { int head,tail,nw,k; head=1;tail=2; q[head]=s; memset(f,false,sizeof(f)); f[s]=true; while(head!=tail) { nw=q[head]; head++; if(head>8000)head=1; k=list[nw]; while(k!=0) { p[s][b[k]]=true; if(f[b[k]]==false) { f[b[k]]=true; q[tail]=b[k]; tail++; if(tail>8000) tail=1; } k=next[k]; } } } int main() { int u,v; //freopen("read.in","r",stdin); init(); memset(h,false,sizeof(h)); scanf("%d",&q1); for(i=1;i<=q1;i++) { scanf("%d%d",&u,&v); if(h[u]==false)

{ bfs(u); h[u]=true; } if(p[u][v])printf("YES\n"); else printf("NO\n"); } return 0; }

P1869:[NOIP1998P1]巧妙填数(它是 P1,我就不说了,太水[枚举之后检验即可]) P1872:站点上下车
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int a,n,m,x,f[21][4]={0}; void find(int b) { f[1][0]=a; f[1][1]=a; f[1][3]=a; f[2][0]=b; f[2][1]=b; f[2][3]=a; for(int i=3;i<n;i++) { f[i][0]=f[i-1][0]+f[i-2][0]; f[i][1]=f[i-1][0]; f[i][3]=f[i-1][3]+f[i][0]-f[i][1]; } f[n][3]=f[n-1][3]; if(f[n][3]==m) {cout<<f[x][3]<<endl;f[0][0]=1;} } int main() { cin>>a>>n>>m>>x; for(int i=0;i<=m;i++) { if(f[0][0]==0) { memset(f,0,sizeof(f)); find(i); } else break; } if(f[0][0]==0) { cout<<"No answer."<<endl;} return 0; //所有的决策了,很好想的(上下车后,上车人数,下车人数,车上人数) //0 表示上车,1 表示下车,2 表示以前上车的总人数,3 表示车上现有人数。 这个状态相当明显了吧

}

P1873:数的连接(P1873:数的连接,这题由于数可能会很长(其实是必然会很长),所以-->使用高精 度!然后从高位开始比较就行了,大的那个一定要先放在前面的) P1878:拦截导弹(和以前一样)输入的方式 While(cin>>?) ?? while(scanf(?)!=EOF) P1883:进制转换(由负进制组成的题)
const char litters[22]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'}; while(nums!=0) { if(nums%rules>=0) { //分成正负两种情况讨论,奇数位和偶数位 //常量表

f[t]=litters[nums%rules]; //cout<<"I'm here t=t+1; nums=(nums-nums%rules)/rules; } else { f[t]=litters[(nums%rules)-rules]; //cout<<"I'm here t=t+1; nums=(nums-(nums%rules-rules))/rules; } } . "<<"----------"<<f[t]<<endl; . "<<"----------"<<f[t]<<endl;

P1889:一元三次方程求解(就是枚举,标程如下)
for (X=-10000;X<=10000;x=(++X)/100.0) { v=a*x*x*x+b*x*x+c*x+d; if (v>=-0.01 && v<=0.01) printf("%.2lf ",x); } //记住这个方式,它是可以固定输出到小数点后…位(本题是 2?%.2) //用整形计算,再除下去

P1965:汪星人入侵(数论数值)其实这道题一开始我想爆搜,但是看着这个题解,我就彻底无语了, 这就是数学大牛 分析:对于这道题,我们只需要求出那些门被开关了奇数次即可。 对于第 i 个门和第 j 只汪星人来说,j 能改变 i 的状态当且仅当 j 是 i 的因数。 (例如 15 号门能被第 1、3、5、15 只汪星人打开。) 那么只需要考虑 1~N 中哪些数的因数有奇数个就可以了。 对于某个数 P,若有 x 是 P 的因数,则 P div x 也是 P 的因数。 所以当且仅当 x=P div x 时,也就是 P=x^2 时,P 有奇数个因数。 于是满足条件的 P 是个完全平方数,而 1~N 中完全平方数有[sqrt(n)]个。 于是答案便是 trunc(sqrt(n))了。 还有一些乱七八糟的: 首先我们回到状态设定的总结哈,我们最需要的是找到一个可以表示任意时刻待求内容的方式。而题 目中常常作为这类状态的是时间,位置,地点,体积,方式,编号??其实就是会随着你由大将问题 化小的过程中,会变化的量,这样你才能用上以前的重叠子。即,你不仅要表示出当前,也要能在以 后为更大范围的状态的更新做出贡献。 另外有的时候你会觉得有些条件很难与表示,而其实这些往往就是应当最为状态出现的啦哈!

上面这句话嘛,我用 IOI 的矿工配餐去解释,(但其实这道题我没写完):红体字部分恰好把那个苛 刻的条件确定了下来。
不说废话,我们设 f[i,pa1,pa2,pb1,pb2]表示经过 i 辆食品车,矿场 1 当前车为 pa1,上一辆车为 pa2,矿场 2 当前车为 pb1,上一 辆车为 pb2 的最优解,显然我们可以从 i-1 的状态递推得到 i 的状态(这里直接给出方程): f[i,s[i],pa1,pb1,pb2]=max{f[i-1,pa1,pa2,pb1,pb2]+w(s[i],pa1,pa2)} f[i,pa1,pa2,s[i],pb1]=max{f[i-1,pa1,pa2,pb1,pb2]+w(s[i],pb1,pb2)} (1<=i<=n ,0<=pa1<=3 ,0<=pa2<=3 ,0<=pb1<=3 ,0<=pb2<=3) 边界条件:f[i,pa1,pa2,pb1,pb2]=-oo;f[0,0,0,0]=0; 其中 w(a,b,c)表示连续 3 次食品车的种类为 a,b,c 时的产煤数目. 也许有人会不理解 pa1,pa2,pb1pb2 为什么会出现 0,其实这是为了防止出现前面运送食品的次数不足两次的情况.有了这一点我 们可以知道上面有几种情况是要排除掉的:(pa1=0)and(pa2>0)或(pb1=0)and(pb2>0)(可以想一下为什么?). 可以发现状态 i 至于 i-1 有关,我们可以使用滚动数组来优化. 时将复杂度 O(256*N),空间复杂度 O(N) 这道题目可以被完美解决了. 对于一个状态和方程我们要尽可能的想这个状态是否有冗余,或者有一定的同性 本状态就有一个重要的同性就是每秒结束后总有一个人在 GO[I] 所以我们可以根据这一同性进行状态的压缩 F[I,X1,X2] x1.x2 代表不在 P[I]的那两个人的位置 此状态就默认了第四维 X3 始终处于 P[I] 这样就成功的完成了压缩 压缩状态~~多多寻找原来状态的通性


推荐相关:

tyvj题解(前80道)[1]

背景 Background NOIP2008 年普及组第一题 描述 Description 每一本正式出版的...背景 Background USACO OCT09 1ST 描述 Description Bessie 那惨无人道的二年级...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com