?
這是一題類似于排列組合的題目吧...遞推狀態(tài)
數(shù)組f[100][100][100][2];表示紅旗數(shù)目，黃旗數(shù)目，顏色改變的次數(shù)，末尾的旗的顏色（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];
}
}
?就拿循環(huán)中的for(int l=1;l<=i;l++)這個循環(huán)說說我自己的想法吧
因為是從上一個狀態(tài)推下來的，k-1這個應(yīng)該沒有問題，那為什么以黃旗結(jié)尾的是加上k-1時以紅旗結(jié)尾的呢？
其實這個也很好理解...改變k-1次時，以紅旗結(jié)尾，改變k次時，當(dāng)然是以黃旗結(jié)尾的了
i-l是啥？枚舉狀態(tài)啊....這個需要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;
}
?
這一題和合并石子有點像，但是不可混為一談...題目的要求是有所不同的，要注意審題
說說這一題吧...這一題也是有很多解法的
因為之前沒有打過優(yōu)先隊列，所以這里算是學(xué)習(xí)了一下吧
?
首先是頭文件#include<queue>
priority_queue<int> qi;//普通的優(yōu)先級隊列，按從大到小排序（默認(rèn)）
priority_queue<int, vector<int>, greater<int> > qi2;//從小到大的優(yōu)先級隊列
//可將greater改為less，即為從大到小
?
然后調(diào)用起來和queue的操作沒有什么區(qū)別
但是注意一下q.top和q.front的使用吧，front不一定是最優(yōu)先的
?
再套上這一題的思路：
每次選最小的兩個數(shù)拿出來，加和后再加入隊列里，排序。
?
這個思路有點類似于貪心思想...很容易證明
因為每次合并都是把之前合并的加上現(xiàn)在的某一堆，所以之前合并的果子越小越優(yōu)
?
附上代碼：
?
#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;
}
?
晚安....
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
