?
這是一題類似于排列組合的題目吧...遞推狀態
數組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; }
?
這一題和合并石子有點像,但是不可混為一談...題目的要求是有所不同的,要注意審題
說說這一題吧...這一題也是有很多解法的
因為之前沒有打過優先隊列,所以這里算是學習了一下吧
?
首先是頭文件#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; }
?
晚安....
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
