No.1 硬幣
#include<bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f3f3f
int main(){
int A[]={2,5,7} ,M;
cin>>M;
int n=3;
int f[M+1];//因為要用到f[M]
f[0]=0;//初始化
for(int i=1;i<=M;i++){
f[i]=MAX;//全部初始化
for(int j=0;j<n;j++){
if(i-A[j]>=0&&i-A[j]!=MAX){//判斷
f[i]=min(f[i-A[j]]+1,f[i]);
}
}
}
if(f[M]==MAX) cout<<"-1"<<endl;
else cout<<f[M]<<endl;
return 0;
}
No.2機器人走到右下角
- 求計數型動態規劃
- 1.確定狀態
- 最后一步可以通過前一步（上或者左）相加
- 2.轉化方程
- f[i][j]=f[i-1][j]+f[i][j-1]
- 3.初始條件及邊界情況
- f[0][0]=1;
- i=0或者j=0時，f[i][j]=1;
- 4.計算順序
- 二維題目：先第一行，，再第二，三行
#include<bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f3f3f
int main(){
int m,n;
cin>>m>>n;
int f[110][110];//f[i][j]指機器人有多少種方式到右下角
for(int i=0;i<m;i++){//行
for(int j=0;j<n;j++){//列
if(i==0||j==0){
f[i][j]=1;
}
else{
f[i][j]=f[i-1][j]+f[i][j-1];
}
}
}
cout<<f[m-1][n-1]<<endl;
return 0;
}
No.3小青蛙跳到最后一塊石頭上
**存在型動態規劃
-
最后一步：跳到n-1
/前一步：跳到j,而且n-1-j<=a[j],所以轉化為能不能跳到j -
轉化方程：
- 初始條件：f[0]=1;
- 所求是f[n-1]
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[n],f[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
f[0]=1;
for(int j=1;j<n;j++){
f[j]=0;
for(int i=0;i<j;i++){
if(f[i]&&j-i<=a[i]){
f[j]=1;
break;
}
}
}
cout<<f[n-1]<<endl;
return 0;
}
~~未完待續，馬上回來~
~~我回來啦~
No.4 最長上升子序列
- 1.確定狀態：
- 2.轉移方程：f[i]=max( f[i], f[j]+1 )
- 3.初始條件：f[i]=1
- 4.計算順序：f[0]----->f[n-1]
#include<bits/stdc++.h>
using namespace std;
int a[100];
int f[100];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
//重點
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++){
if(a[i]>a[j]){
f[i]=max(f[i],f[j]+1);
}
}
}
//找出最大的上升序列
int maxx=f[0];
for(int i=1;i<n;i++){
if(f[i]>f[i-1]) maxx=f[i];
}
cout<<maxx<<endl;
return 0;
}
No.5最大連續乘積
emmmm開始的時候混了，要是最大乘積的話只要篩選一下負數有多少個不就🆗了，所以肯定要考察連續乘積，和上升序列&連續上升序列不一樣的地方，
注意負負得正，需要記下最大和最小值，我發現用max,min好方便哈哈哈，不過注意一次只能比較兩個
#include<bits/stdc++.h>
using namespace std;
int a[100];
int ma[100],mi[100];
int main(){
int n,maxval;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
maxval=ma[0]=mi[0]=a[0];//初始化
for(int i=1;i<n;i++){//注意昂，只能同時比較兩個大小
ma[i]=max(max(ma[i-1]*a[i],mi[i-1]*a[i]),a[i]);
mi[i]=min(min(ma[i-1]*a[i],mi[i-1]*a[i]),a[i]);
maxval=max(maxval,ma[i]);
}
cout<<maxval<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/167056.html
標籤：其他