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] 这样就成功的完成了压缩 压缩状态~~多多寻找原来状态的通性


赞助商链接
推荐相关:

信息学奥赛(NOIP)必看经典书目汇总

知识点大杂烩,部分内容由学生撰写,但是对初赛知识点...题库方面首推 USACO(美国的赛题) ,usaco 写完了...3、国内广受 NOIP 级别选手喜欢的国内 OJ(Tyvj、...


noip普及组复赛模拟试题19

一个单词的权值定义为单词所含的字母的权 值之和。你的任务是按权值降序(从...【输入样例】10 10 noip noi ceoi ctsc apoi usaco nocow vijos crack tyvj...


NOIP的DP总结之DP类型

USACO Raucous Rockers (多个背包,不可以重复放物品,但放物品的顺序有限制。 )...题目:砝码秤重,tyvj1086,zoj2156,poj2392,hdu1085 Poj1014,divide(见 dp2) ...


信息学奥赛(NOIP)必看经典书目汇总

(推荐指数:4 颗星) 曹文,吴涛编著,知识点大杂烩,...题库方面首推 USACO(美国的赛题),usaco 写完了一...国内广受 NOIP 级别选手喜欢的国内 OJ(Tyvj、Code...


C++NOIP模拟试题

【输入样例】 输入样例】 10 10 noip noi ceoi ctsc apoi usaco nocow vijos tyvj 【输出样例】 输出样例】 ctsc 27 vijos 26 nocow 23 crack 23 usaco 22...


百度NOIP吧编程挑战赛

【输入样例】 输入样例】 10 10 noip noi ceoi ctsc apoi usaco nocow vijos tyvj 【输出样例】 输出样例】 ctsc 27 vijos 26 nocow 23 crack 23 usaco 22...


信息学奥赛(NOIP)必看经典书目汇总

知识点大杂烩,部分内容由学生撰写,但是对初赛知识点...题库方面首推 USACO(美国的赛题) ,usaco 写完了...3、国内广受 NOIP 级别选手喜欢的国内 OJ(Tyvj、...

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