首页 > 代码库 > AHOI1997彩旗飘飘 VIJOS1097合并果子（noip2007)
AHOI1997彩旗飘飘 VIJOS1097合并果子（noip2007)
为了防止手感下滑，就把整理长乐集训题题解的脚步给放慢了...
前几天vj死了好久，就刷起了rqnoj...里面题目质量有的太烂了，而且第一页的题号还是不连续的！！
晚上vj修好后刷了一题，还有之前刷的ahoi的题也在这里说一下吧...也无聊刷了一些特别水的题目就懒得说了...
AHOI彩旗飘飘
这是一题类似于排列组合的题目吧...递推状态
数组f[100][100][100][2];表示红旗数目，黄旗数目，颜色改变的次数，末尾的旗的颜色（0为黄，1为红）
之后就是如何写递推式了：
for(int k=2;k<=m;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ for(int l=1;l<=i;l++){ f[i][j][k][0]+=f[i-l][j][k-1][1]; } for(int l=1;l<=j;l++){ f[i][j][k][1]+=f[i][j-l][k-1][0]; } }就拿循环中的for(int l=1;l<=i;l++)这个循环说说我自己的想法吧
因为是从上一个状态推下来的，k-1这个应该没有问题，那为什么以黄旗结尾的是加上k-1时以红旗结尾的呢？
其实这个也很好理解...改变k-1次时，以红旗结尾，改变k次时，当然是以黄旗结尾的了
i-l是啥？枚举状态啊....这个需要feel
附上完整代码：
#include<cstdio>#include<iostream>using namespace std;int n,m;int f[100][100][100][2];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ f[i][j][1][0]=f[i][j][1][1]=1; } for(int k=2;k<=m;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ for(int l=1;l<=i;l++){ f[i][j][k][0]+=f[i-l][j][k-1][1]; } for(int l=1;l<=j;l++){ f[i][j][k][1]+=f[i][j-l][k-1][0]; } } cout<<f[n][n][m][1]+f[n][n][m][0]; return 0;}
VIJOS1097合并果子
这一题和合并石子有点像，但是不可混为一谈...题目的要求是有所不同的，要注意审题
说说这一题吧...这一题也是有很多解法的
因为之前没有打过优先队列，所以这里算是学习了一下吧
首先是头文件#include<queue>
priority_queue<int> qi;//普通的优先级队列，按从大到小排序（默认）
priority_queue<int, vector<int>, greater<int> > qi2;//从小到大的优先级队列
//可将greater改为less，即为从大到小
然后调用起来和queue的操作没有什么区别
但是注意一下q.top和q.front的使用吧，front不一定是最优先的
再套上这一题的思路：
每次选最小的两个数拿出来，加和后再加入队列里，排序。
这个思路有点类似于贪心思想...很容易证明
因为每次合并都是把之前合并的加上现在的某一堆，所以之前合并的果子越小越优
附上代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<queue>using namespace std;priority_queue<int, vector<int>, greater<int> >q;int n,x,y;long long ans=0;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&x); q.push(x); } while(!q.empty()){ x=q.top(); q.pop(); if(q.empty()) break; y=q.top(); q.pop(); q.push(x+y); ans+=(x+y); } cout<<ans; return 0;}
晚安....
AHOI1997彩旗飘飘 VIJOS1097合并果子（noip2007)