最小m段和問題
【問題描述】
給定 n 個整陣列成的序列，現在要求將序列分割為 m 段，每段子序列中的數在原序列
中連續排列，如何分割才能使這 m段子序列的和的最大值達到最小？
演算法設計：
給定 n 個整陣列成的序列,計算該序列的最優 m段分割，使 m段子序列的和的最大值達到最小，
【輸入形式】
輸入資料：第 1 行中有 2 個正整數 n 和 m，正整數 n 是序列的長度；正整數 m是分割的段數，接下來的一行中有 n 個整數，
【輸出形式】
將計算結果輸出：第 1 行中的數是計算出的 m段子序列的和的最大值的最小值，
【樣例輸入】
1 1
10
【樣例輸出】
10
/*
--------------------------------------
--------------------------------------
------Problem: 8918.最小m段和問題----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,a[1005];
int dp[1005][1005];
int sum[1005][1005];
int main()
{
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
dp[i][j] = 1000000000;
for(int i=1; i<=n; i++) {
int num = 0;
for(int j=i; j<=n; j++) {
num += a[j];
sum[i][j] = num;
}
dp[i][1] = sum[1][i];
}
for(int i=2; i<=n; i++) {
for(int j=2; j<=i && j<=m; j++) {
int p;
for(int k=1; k<i; k++)
dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[k + 1][i]));
}
}
cout << dp[n][m] << endl;
return 0;
}
最大 k 乘積問題
【問題描述】
設 I 是一個 n 位十進制整數，如果將 I 劃分為 k 段，則可得到 k 個整數，這 k 個整數的
乘積稱為 I 的一個 k 乘積，試設計一個演算法，對于給定的 I 和 k，求出 I 的最大 k 乘積，
演算法設計：
對于給定的 I 和 k，計算 I 的最大 k 乘積，
【輸入形式】
輸入資料：第 1 行中有 2 個正整數 n 和 k，正整數 n 是序列
的長度；正整數 k 是分割的段數，
接下來的一行中是一個 n 位十進制整數，（n<=10）
【輸出形式】
將計算結果輸出：第 1 行中的數是計算出的最大 k 乘積，
【樣例輸入】
2 1
15
【樣例輸出】
15
/*
--------------------------------------
--------------------------------------
-------Problem: 8917.最大k乘積問題----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int dp[15][15]; //最大乘積陣列
char numstr[15];
int num[15];
int getValue(int i,int j) {
int sum = 0;
for(int k=i; k<j; k++) {
sum += num[k];
sum *= 10;
}
return sum + num[j];
}
void dpAlgo(int l,int k) {
for(int i=1; i<=l; i++)
dp[i][1] = getValue(1,i);
for(int i=0; i<=l; i++) {
for(int j=2; j<=k; j++) {
int temp = 0;
for(int d=1; d<i; d++)
temp = max(temp,dp[d][j-1] * getValue(d+1,i));
dp[i][j] = temp;
}
}
}
int main()
{
int l,k;
cin>>l>>k>>numstr;
for(int i=0; i<l; i++)
num[i+1] = numstr[i] - '0';
dpAlgo(l,k);
cout << dp[l][k];
return 0;
}
石子合并問題
【問題描述】
在一個圓形操場的四周擺放著 n 堆石子，現要將石子有次序地合并成一堆，規定每次只能選相鄰的 2 堆石子合并成新的一堆，并將新的一堆石子數記為該次合并的得分，試設計一個演算法，計算出將 n 堆石子合并成一堆的最小得分和最大得分，
演算法設計：
對于給定 n 堆石子,計算合并成一堆的最小得分和最大得分，
【輸入形式】
輸入資料：第 1 行是正整數 n，1≤n≤100，表示有 n 堆石子，
第二行有 n 個數，分別表示每堆石子的個數，
【輸出形式】
將計算結果輸出：第 1 行中的數是最小得分；第 2 行中的數是最大得分，
【樣例輸入】
4
4 4 5 9
【樣例輸出】
43
54
/*
--------------------------------------
--------------------------------------
--------Problem: 8920.石子合并問題----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
int n,m,ans1,ans2;
int A[205],f1[205][205],f2[205][205];
int dfs1(int L,int R){ //求出最小得分
if(f1[L][R])return f1[L][R]; //已保存的狀態不必搜索
if(L==R) return f1[L][R]=0; //L==R時回傳0
int res=INF; //初始值賦為最大值以求最小值
for(int k=L;k<R;k++) //列舉K搜索
res=min(res,dfs1(L,k)+dfs1(k+1,R)+A[R]-A[L-1]);
return f1[L][R]=res; //記錄狀態
}
int dfs2(int L,int R){ //求出最大得分
if(f2[L][R])return f2[L][R];
if(L==R) return f2[L][R]=0; //若初始值為0可省略該句
int res=0; //初始值設為0
for(int k=L;k<R;k++)
res=max(res,dfs2(L,k)+dfs2(k+1,R)+A[R]-A[L-1]);
return f2[L][R]=res;
}
int main(){
std::ios::sync_with_stdio(false);//取消cin與stdin同步,加速讀入
cin>>n;
for(int i=1;i<=n;i++){
cin>>A[i];
A[i+n]=A[i]; //因為是環所以保存為長度為2n的鏈以保證不會漏解
}
for(int i=1;i<=2*n;i++) //求出前綴和
A[i]+=A[i-1];
dfs1(1,2*n);dfs2(1,2*n); //搜索出1-2n的最大得分與最小得分
ans1=INF; ans2=0;
for(int i=1;i<=n;i++){
ans1=min(f1[i][n+i-1],ans1);//選出答案
ans2=max(f2[i][n+i-1],ans2);
}
cout<<ans1<<"\n"<<ans2;
return 0;
}
最大長方體問題
【問題描述】
一個長，寬，高分別為 m,n,p 的長方體被分割成個 mnp 個小立方體，每個小立方體內有一個整數，試設計一個演算法，計算出所給長方體的最大子長方體，子長方體的大小由它所含所有整數之和確定，
演算法設計：
對于給定的長，寬，高分別為 m,n,p 的長方體，計算最大子長方體的大小，
【輸入形式】
輸入資料：第 1 行是 3 個正整數 m,n,p，1≤m,n,p≤50，接下來 m*n 行每行 p 個正整數，表示小立方體中的數，
【輸出形式】
將計算結果輸出：第 1 行中的數是計算出的最大子長方體的大小，
【樣例輸入】
3 3 3
0 -1 2
1 2 2
1 1 -2
-2 -1 -1
-3 3 -2
-2 -3 1
-2 3 3
0 1 3
2 1 -3
【樣例輸出】
14
/*
--------------------------------------
--------------------------------------
-------Problem: 8916.最大長方體問題---
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int maxsum(int n,int *a)
{
int sum=0,b=0;
for (int i=1; i<=n; i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;//記錄最大值
}
return sum;
}
int maxsum2(int m,int n, int **a){
int sum=0;
int *b=new int [n+1];
for (int i=1; i<=m; i++) {
for(int k=1; k<=n; k++)
b[k]=0;//置0
for(int j=i; j<=m; j++) {//動規思想，將m分成1~i和i+1~m兩段
for (int k=1; k<=n; k++)
b[k] += a[j][k];
int max=maxsum(n,b);
if(max>sum) sum=max;
}
}
return sum;
}
int maxsum3(int m,int n,int p,int ***a)
{
int sum=0;
int **c=new int*[n+1];
for(int i=1; i<=n; i++) c[i]=new int [p+1];
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
for(int k=1; k<=p ; k++) c[j][k]=0;//置0
for (int l=i; l<=m; l++) {//和二維的思想一樣
for(int j=1; j<=n; j++)
for(int k=1; k<=p ; k++) c[j][k]+=a[l][j][k];
int max=maxsum2(n,p,c);
if(max>sum) sum=max;
}
}
return sum;
}
int main()
{
int m,n,p,***a;
cin>>m>>n>>p;
a=new int**[m+1];
for(int i=1; i<=m; i++) a[i]=new int*[n+1]; //一維
for(int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
a[i][j]=new int[p+1]; //二維
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
for(int k=1; k<=p; k++)
cin>>a[i][j][k]; //三維
cout<<maxsum3(m,n,p,a);
}
序關系計數問題
【問題描述】
用關系“<”和“=”將 3 個數 A、B 和 C 依序排列時有 13 種不同的序關系：A=B=C，A=B<C，A<B=C，A<B<C，A<C<B，A=C<B，B<A=C，B<A<C，B<C<A，B=C<A，C<A=B，C<A<B，C<B<A，將n 個數（1 ≤ n ≤50）依序排列時有多少種序關系，
演算法設計：
計算出將n 個數（1 ≤ n ≤50）依序排列時有多少種序關系，
【輸入形式】
輸入資料：輸入資料有多行，每行提供一個數n ，
【輸出形式】
將找到的序關系數輸出：一行一個，
【樣例輸入】
3
5
【樣例輸出】
13
541
/*
--------------------------------------
--------------------------------------
-------Problem: 8923.序關系計數問題---
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
#define MAX_N 51
using namespace std;
__int64 dp[MAX_N][MAX_N]; //dp[i][j]：i個數，有j個‘<’鏈接，共有多少種情況
int main()
{
int n,i,j;
for(i=0; i<MAX_N; i++) dp[i][0]=1;
for(i=0; i<MAX_N; i++)
for(j=1; j<i; j++)
dp[i][j] = (j+1)*(dp[i-1][j]+dp[i-1][j-1]);
for(i=0; i<MAX_N; i++)
for(j=0; j<i; j++)
dp[i][i] += dp[i][j]; //dp[i][i]存放每一行的和
while(scanf("%d",&n)==1){
printf("%I64d\n",dp[n][n]);
}
return 0;
}
汽車加油行駛問題
【問題描述】
給定一個N*N 的方形網格，設其左上角為起點，坐標為（1,1），X 軸向右為正，Y 軸向下為正，每個方格邊長為1，一輛汽車從起點出發駛向右下角終點，其坐標為（N,N），在若干個網格交叉點處，設定了油庫，可供汽車在行駛途中加油，汽車在行駛程序中應遵守
如下規則：（1）汽車只能沿網格邊行駛，裝滿油后能行駛K 條網格邊，出發時汽車已裝滿油，在起點與終點處不設油庫，（2）當汽車行駛經過一條網格邊時，若其 X 坐標或 Y 坐標減小，則應付費用B，否則免付費用，（3）汽車在行駛程序中遇油庫則應加滿油并付加油費用A，（4）在需要時可在網格點處增設油庫，并付增設油庫費用C（不含加油費用A），（5）(1)～(4)中的各數N、K、A、B、C均為正整數，
演算法設計：
求汽車從起點出發到達終點的一條所付費用最少的行駛路線，
【輸入形式】
輸入資料：
第一行是N，K，A，B，C的值，2 ≤ N ≤ 100，2 ≤ K ≤ 10，第二行起是一個N*N 的0-1方陣，每行N 個值，至N+1行結束，方陣的第i行第j 列處的值為1 表示在網格交叉點（i，j）處設定了一個油庫，為0 時表示未設油庫，各行相鄰的2 個數以空格分隔，
【輸出形式】
將找到的最優行駛路線所需的費用，即最小費用輸出：第1行中的數是最小費用值，
【樣例輸入】
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0
【樣例輸出】
12
/*
--------------------------------------
--------------------------------------
-----Problem: 8910.汽車加油行駛問題---
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
#define MAX 120
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line
{
int v,next,w;
}e[MAX*MAX*MAX];
int h[MAX*MAX],cnt=1,tot;
int m[MAX*MAX],g[MAX][MAX],n,K,A,B,C;
bool vis[MAX*MAX][15];
inline void Add(int u,int v,int w)
{
e[cnt]=(Line){v,h[u],w};h[u]=cnt++;
}
int dis[MAX*MAX][15];
void SPFA()
{
memset(dis,63,sizeof(dis));
dis[g[1][1]][K]=0;
queue<int> Q,Q1;
Q.push(g[1][1]);Q1.push(K);
while(!Q.empty())
{
int u=Q.front(),t=Q1.front();
Q.pop();Q1.pop();
if(t!=0)
{
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v,gg=t-1,Dis=dis[u][t]+e[i].w;
if(m[v])gg=K,Dis+=A;
if(dis[v][gg]>Dis)
{
dis[v][gg]=Dis;
if(!vis[v][gg])vis[v][gg]=true,Q.push(v),Q1.push(gg);
}
}
}
int v=u,gg=K,Dis=dis[u][t]+C+A;
if(dis[v][gg]>Dis)
{
dis[v][gg]=Dis;
if(!vis[v][gg])vis[v][gg]=true,Q.push(v),Q1.push(gg);
}
vis[u][t]=false;
}
}
int main()
{
n=read();K=read();A=read();B=read();C=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
g[i][j]=++tot,m[g[i][j]]=read();;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(i!=n) Add(g[i][j],g[i+1][j],0);
if(j!=n) Add(g[i][j],g[i][j+1],0);
if(i!=1) Add(g[i][j],g[i-1][j],B);
if(j!=1) Add(g[i][j],g[i][j-1],B);
}
SPFA();
int ans=1e9;
for(int i=0;i<=K;++i)ans=min(ans,dis[g[n][n]][i]);
printf("%d\n",ans);
return 0;
}
最少硬幣問題
【問題描述】
設有 n 種不同面值的硬幣，各硬幣的面值存于陣列 T[1:n]中，現要用這些面值的硬幣來找錢，可以使用的各種面值的硬幣個數存于陣列 Coins[1:n]中，對任意錢數 0≤m≤20001，設計一個用最少硬幣找錢 m 的方法，
演算法設計：
對于給定的 1≤n≤10，硬幣面值陣列 T 和可以使用的各種面值的硬幣個數陣列 Coins，以及錢數 m，0≤m≤20001，計算找錢 m的最少硬幣數，
【輸入形式】
輸入資料：第一行中只有 1 個整數給出n 的值,第 2 行起每
行 2 個數，分別是 T[j]和 Coins[j]，最后 1 行是要找的錢數 m，
【輸出形式】
將計算出的最少硬幣數輸出，問題無解時輸出-1，
【樣例輸入】
3
1 3
2 3
5 3
18
【樣例輸出】
5
/*
--------------------------------------
--------------------------------------
--------Problem: 8913.最少硬幣問題----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
/*多重背包(硬幣種類有限制，硬幣數目有限制)*/
#include <iostream>
using namespace std;
const int maxvalue = 20001;
const int coinnum = 15;
int mymin(int a,int b){
return a < b ? a : b;
}
int main()
{
int n;
cin >> n;
int coin[coinnum];
int coincount[coinnum];
for(int i=0; i<n; i++)
{
cin >> coin[i];
cin >> coincount[i];
}
int m;
cin >> m;
//錢數為dp[i]是的硬幣數目
int *dp = new int[maxvalue]();
//重點錯誤
//for(int i=0; i<=m; i++)是錯的
for(int i=1; i<=m; i++) dp[i] = maxvalue;
int i,j,k;
for(i=0; i<n; i++)//硬幣面值的種數
{
for(j=1; j<=coincount[i]; j++)//硬幣的面值的個數
{
for(k=m; k>=coin[i]; k--) //動態遷移方程為
dp[k] = mymin(dp[k - coin[i]] + 1, dp[k]);
}
}
if(dp[m] == maxvalue)
cout << -1 << endl;
else cout << dp[m] << endl;
return 0;
}
租用游艇問題
【問題描述】
長江游艇俱樂部在長江上設定了 n 個游艇出租站 1，2，…，n，游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇，游艇出租站 i 到游艇出租站 j 之間的租金為 r(i,j),1≤i<j≤n，試設計一個演算法，計算出從游艇出租站 1 到游艇出租站 n 所需的最少租金，
演算法設計：
對于給定的游艇出租站 i 到游艇出租站 j 之間的租金為 r(i,j),1≤i<j≤n，計算從游艇出租站 1 到游艇出租站 n 所需的最少租金，
【輸入形式】
輸入資料：第 1 行中有 1 個正整數 n（n<=200），表示有 n個游艇出租站，接下來的 n-1 行是 r(i,j),1≤i<j≤n，
【輸出形式】
將計算出的從游艇出租站 1 到游艇出租站 n 所需的最少租金輸出，
【樣例輸入】
3
5 15
7
【樣例輸出】
12
/*
--------------------------------------
--------------------------------------
--------Problem: 8924.租用游艇問題----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n,v[222][222];
int dp[222];//dp[i]表示到第i個游艇出租站所需的最少租金
int main()
{
scanf("%d",&n);
for(int i=1; i<n; i++)
for(int j=i+1; j<=n; j++)
scanf("%d",&v[i][j]);
memset(dp,INF,sizeof(dp));
dp[1]=0;
for(int i=2; i<=n; i++)
for(int j=1; j<i; j++)
dp[i] = min(dp[i],dp[j]+v[j][i]);
printf("%d\n",dp[n]);
return 0;
}
紅黑樹的紅色內結點問題
【問題描述】
紅黑樹是一類特殊的二叉搜索樹，其中每個結點被“染成”紅色或黑色，若將二叉搜索樹結點中的空指標看作是指向一個空結點，則稱這類空結點為二叉搜索樹的前端結點，并規定所有前端結點的高度為-1，
一棵紅黑樹是滿足下面“紅黑性質”染色二叉搜索樹：
(1)每個結點被染成紅色或黑色；
(2)每個前端結點為黑色結點；
(3)任一紅結點的兒子結點均為黑結點；
(4)在從任一結點到其子孫前端結點的所有路徑上具有相同的黑結點數，
從紅黑樹中任一結點 x 出發(不包括結點 x)，到達一個前端結點的任意一條路徑上的黑結點個數稱為結點 x 的黑高度，記作 bh(x)，紅黑樹的黑高度定義為其根結點的黑高度，圖示的二叉搜索樹是一棵紅黑樹，標在結點旁邊的數字是相應結點的黑高度，
演算法設計：
給定正整數 n，試設計一個演算法，計算出在所有含有 n 個結點的紅黑樹中，紅色內結點個數的最小值和最大值，
【輸入形式】
輸入資料：第一行是正整數 n，1<n<5000，
【輸出形式】
將紅色內結點個數的最小值和最大值輸出：第 1 行是最小值，第 2行是最大值，
【樣例輸入】
8
【樣例輸出】
1
4
/*
--------------------------------------
--------------------------------------
------8830. 紅黑樹的紅色內結點問題----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int main()
{
scanf("%d",&n);
m=n+1;
while(m>1) {
ans+=m&1;m>>=1;
}
printf("%d\n",ans);
m=n+1;ans=0;
while(m>1)
{
if(m==2) ans++;
if((m&3)==1) ans+=m/4*2-1,m/=4,m++;
else if((m&3)==2) ans+=m/4*2,m/=4,m++;
else if((m&3)==3) ans+=m/4*2+1,m/=4,m++;
else ans+=m/4*2,m/=4;
}
printf("%d\n",ans);
return 0;
}
編輯距離問題
【問題描述】
設 A 和 B 是 2 個字串，要用最少的字符操作將字串 A 轉換為字串 B，這里所說的字符操作包括
(1)洗掉一個字符；
(2)插入一個字符；
(3)將一個字符改為另一個字符，
將字串 A 變換為字串 B 所用的最少字符運算元稱為字串 A 到 B 的編輯距離，記為d(A,B)，試設計一個有效演算法，對任給的2個字串A和B，計算出它們的編輯距離d(A,B)，
演算法設計：
對于給定的字串 A 和字串 B，計算其編輯距離 d(A,B)，
【輸入形式】
輸入資料：第一行是字串 A，檔案的第二行是字串 B，
【輸出形式】
將編輯距離 d(A,B)輸出到第 1 行中，
【樣例輸入】
fxpimu
xwrs
【樣例輸出】
5
/*
--------------------------------------
--------------------------------------
---------------8829. 編輯距離問題-----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int d[2005][2005];
/*
輸入的兩個字符陣列為a[], b[]，從下標為0開始初始化
長度分別為length_a, length_b
陣列d[m][n]存放從a[1:m] 變為 b[1:n]所需要的最少操作
遞回公式：
d[i][j] = 0, i=0或j=0 時(即陣列的第一行和第一列均為0)
1<=i<=length_a， 1<=j<=length_b
d[i][j] = d[i-1][j-1], a[i-1] == b[j-1]
d[i][j] = min(d[i-1][j-1]+1, d[i][j-1]+1, d[i-1][j]+1), a[i-1] != b[j-1]
最優值：d[length_a][length_b]
*/
int min(int a, int b, int c)
{
int temp = a;
if(temp>b) temp = b;
if(temp>c) temp =c;
return temp;
}
int edit(char *a, char *b)
{
int length_a = strlen(a);
int length_b = strlen(b);
for(int i=0; i<=length_a; i++) d[i][0] = i;
for(int i=0; i<=length_b; i++) d[0][i] = i;
for(int i=1; i<=length_a; i++) {
for(int j=1; j<=length_b; j++) {
if(a[i-1] == b[j-1])
d[i][j] = min(d[i-1][j-1], d[i][j-1]+1, d[i-1][j]+1);
else
d[i][j] = min(d[i-1][j-1]+1, d[i][j-1]+1, d[i-1][j]+1);
}
}
return d[length_a][length_b];
}
int main()
{
char a[2000], b[2000];
cin>>a>>b;
cout<<edit(a,b);
}
圈乘運算問題
【問題描述】
關于整數的 2 元圈乘運算?定義為（X?Y）=10 進制整數 X 的各位數字之和 * 10 進制整數 Y 的最大數字+Y 的最小數字，例如,（9?30）=9*3+0=27，對于給定的 10 進制整數 X 和 K，由 X 和?運算可以組成各種不同的運算式，試設計一個演算法，計算出由 X 和?運算組成的值為 K 的運算式最少需用多少個?運算，
演算法設計：
給定 10 進制整數 X 和 K (1≤X,K≤1020) ，計算由 X 和?運算組成的值為 K 的運算式最少需用多少個?運算，
【輸入形式】
輸入資料：每一行有 2 個 10 進制整數 X 和 K，最后一行是 0 0（以0 0結束），
【輸出形式】
將找到的最少?運算個數輸出，
【樣例輸入】
3 12
0 0
【樣例輸出】
1
這題TLE了，明天藍橋，之后AC了再補上
/*
--------------------------------------
--------------------------------------
---------------8911. 圈乘運算問題-----
--------------------------------------
----------------------Author----------
--------------------------------------
----------------------XZITXX----------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX=81*30+9,MIN=-1;
int NumLen(int x){//統計位數
int len = 0;
while (x>0){
len++;
x /= 10;
}
return len;
}
void Init(int* a, int x){//作初始化
int min = 10;
int max = 0;
int num = 0;
int tend = 0;
while (x > 0){
tend = x % 10;
x /= 10;
num += tend;
if (tend > max){
max = tend;
}
if (tend < min){
min = tend;
}
}
a[0] = MAX;//存放最小圈乘次數
a[1] = num;//存放各位數之和
a[2] = min;//存放最小的數
a[3] = max;//存放最大的數
}
int main()
{
int x,k;
while(~scanf("%d%d",&x,&k)&&x!=0&&k!=0)
{
int n = NumLen(x);//表示x的位數
int m = 81*n+9;//b最小可以2為陣列合，最大為9，最小為9.所以（x的各位數相加）*9+9；x的各位數相加最大為9*n；
if(m<177){//因為y可能是2位數，導致1位數的x圈乘后的結果為2位數
m = 177;
}
if (k>m){//若k大于x的最大圈乘數則退出
return -1;
}
int** r = new int*[m+2];//建立二維陣列
for (int i=0; i<m+1; i++){//遍歷每
r[i] = new int[4];
Init(r[i],i);
}
r[m+1] = new int[4];
Init(r[m+1], x);//將起始x寫到陣列的最后
r[m+1][0] = 0;//變成自己不需要圈乘
//開始操作
int flag = 1;
while (flag){//不斷在序列中更新
flag = 0;
for (int i=1; i<=m+1; i++){//尋找X
if (r[i][0] < MAX){
for (int j=1; j<=m+1; j++){//尋找Y
if (r[j][0] < MAX){
int tend = r[i][1] * r[j][3] + r[j][2];//計算圈乘結果
if (r[tend][0]>r[i][0]+r[j][0]+1){//與原來的圈乘生產該數的次數對比找最小
flag = 1;//若有變化則更新x的尋值
r[tend][0] = r[i][0] + r[j][0] + 1; //r[i][0]為得到x的圈乘次數,r[j][0]位得到y的圈乘次數
}//endif
}//endif
}
}//endif
}
}
cout << r[k][0] << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/179650.html
標籤：AI
上一篇：總有開始，開花亦結果