列舉分為暴力列舉和優列舉與模擬列舉。
暴力列舉：例題
火柴棒題目描述
給你n根火柴棍，你可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數（若該數非零，則最高位不能是0）。用火柴棍拼數字0-9的拼法如圖所示：
注意：
加號與等號各自需要兩根火柴棍
如果A≠B，則A+B=C與B+A=C視為不同的等式（A、B、C>=0）
n根火柴棍必須全部用上
輸入格式
輸入檔案matches.in共一行，有一個整數n（n<=24）。
輸出格式
輸出檔案matches.out共一行，表示能拼成的不同等式的數目。
樣例資料
input
Input 1:
14
Input 2:
18
output
Output 1:
2
Output 2:
9
資料規模與約定
時間限制：1s
空間限制：256MB
注釋
【輸入輸出樣例1解釋】
2個等式為0+1=1和1+0=1。
【輸入輸出樣例2解釋】
9個等式為：
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
1. 輸入部分（預處理）
6,2,5,5,4,5,6,3,7,6指的是每個數字的所對應的火柴棒根數
int n;
int stick[1500]={6,2,5,5,4,5,6,3,7,6};
cin>>n; n-=4;
2.列舉：
for (int i=10;i<=2222;i++)
stick[i]=stick[i/10]+stick[i%10];
3.判別：
for(int A=0;A<=1111;A++)
for (int B=0;B<=1111;B++)
{
int cnum=n-stick[A]-stick[B];
if (cnum<=0) continue;
if (cnum==stick[A+B]) ans++;
}
cout<<ans<<endl;
完整代碼：
#include<bits/stdc++.h>
using namespace std;
int stick[2500]={6,2,5,5,4,5,6,3,7,6};
int main()
{
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
int n;
cin>>n;
n-=4;
for(int i=10;i<=2222;i++)
{
stick[i]=stick[i/10]+stick[i%10];
}
int ans=0;
for(int i=0;i<=1111;i++)
{
for (int j=0;j<=1111;j++)
{
int cnum=n-stick[i]-stick[j];
if (cnum<=0) continue;
if (cnum==stick[i+j]) ans++;
}
}
cout<<ans<<endl;
return 0;
}
優化列舉：
最大連續和
時間限制：1s 空間限制：256MB 輸入檔案：profits.in 輸出檔案：profits.out
題目描述
給定N個數，求這N(1 <=N <= 100,000) 個數的某個連續子序列的累加和，保證這個連續子序列的累加和最大。
輸入格式
第一行：一個整數N。(1 <=N <= 100,000) 接下來N行，每行一個整數P_i(-1,000 <= P_i <= 1,000)。表示第i個數。
輸出格式
一個整數，表示子序列的最大連續累加和。
樣例資料
input
7
-3
4
9
-2
-5
8
-3
output
14
資料規模與約定
20% 資料保證 n≤20
60%資料保證 n≤5000
100% 資料保證 n≤100000
時間限制：1s
空間限制：256MB
注釋
(4, 9, -2, -5, 8) => 14. 子序列不能為空！
1.定義：
int sum=0;
ans=-100000000;
2.判別：
for (int i=1;i<=n;i++)
{
sum+=a[i];
if (sum>ans) ans=sum;
if (sum<0) sum=0;
}
完整代碼：
#include<bits/stdc++.h>
using namespace std;
int a[100000];
int main()
{
freopen("profits.in","r",stdin);
freopen("profits.out","w",stdout);
int sum=0;
int ans=-100000000;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for (int i=1;i<=n;i++)
{
sum+=a[i];
if (sum>ans) ans=sum;
if (sum<0) sum=0;
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/268078.html
標籤：C++ 語言
上一篇：C中將字串轉uint8