s and t are two strings.
Change string s into string t in the least steps.
In each step you can insert or delete a char of the string.
INPUT n1 s
n2 t
n1 is the length of string s
n2 is the length of string t
OUT the least steps
exp:
INPUT 4 abcd
6 aefbhd
OUT 4
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int map[100];
int i,j,result[100];
int n1,n2,nc;
int main(){
cin>>n1>>s1>>n2>>s2;
nc=0;
for (i=0;i<n1;i++){
if ((j=s2.find(s1[i]))>=0){
map[nc]=j;
s2.replace(j,1," ");
nc++;
}
}
result[nc-1]=1;
for (i=nc-2;i>=0;i--){
for (j=i+1;j<nc;j++) if ((map[i]<map[j])&&(result[i]<result[j])) result[i]=result[j];
result[i]++;
}
j=0;
for (i=0;i<nc;i++) if(result[i]>j) j=result[i];
cout<<n1+n2-j-j;
system("pause");
return 0;
}
題記：
Python是荷蘭人寫(xiě)的，Ruby是日本人寫(xiě)的，Lua是巴西人寫(xiě)的，我這個(gè)中國(guó)人只能在這里臉紅。
——CSDN主編 孟巖
不打算自討沒(méi)趣地寫(xiě)個(gè)要超過(guò)Python,Ruby,Lua的腳本引擎，以鍛煉能力為主。
估計(jì)完成以后和Lua有點(diǎn)像，宗旨是：以比Lua更短為榮，以比Python更長(zhǎng)為恥 :-)
┏━┓ ┏━━┓ ┏┓
┃┃┣━┳━┫━━╋━┳┳╋╋━┳━━┓
┃ ┫━┃┃┣━━┃┣┫┏┫┃┃┣┓┏┛
┗┻┻┻┫┏┻━━┻━┻┛┗┫┏┛┗┛
┗┛ ┗┛
引擎就叫RapScript好了(Ruby,Lua,Python 加一起)
附上題目：
在一個(gè)圓形操場(chǎng)的四周擺放著n堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。
/*
Name: Stone Problem
Copyleft: www.graptor.com
Author: Bill Hsu
Date: 27-04-08 15:15
*/
#include <iostream>
#include <string>
#include <fstream>
#define MAX 100
#define MAXint 1000
using namespace std;
int i,j;//循環(huán)用的
ifstream in("in.txt");
ofstream out ("out.txt");
int f[MAX][MAX];//f[i][j]表示從i起取j堆的最大值
int sum[MAX][MAX];//sum[i][j]表示從i起取j堆的和
int num[MAX];
int main()
{
int n;
in >>n;
for(i=1;i<=n;i++)
{
in >>num[i];
sum[i][1]=num[i];
f[i][1]=0;
}//end for
for (j=2;j<=n;++j)
{
cout <<endl<<j<<endl<<endl;
for(i=1;i<=n;++i)
{
cout <<(sum[i][j]=num[i]+sum[i%n+1][j-1])<<endl;
}//end for i
}//end for j
int k,x,t;
for (j=2;j<=n;j++)
{
for(i=1;i<=n;i++)
{
f[i][j]=MAXint;
t=sum[i][j];
for(k=1;k<=j-1;k++)
{
x=(i+k-1)%n+1;
if(f[i][k]+f[x][j-k]+t<f[i][j])
f[i][j]=f[i][k]+f[x][j-k]+t;
}//end for k
cout <<f[i][j]<<endl;
}//end for i
}//end for j
int tmp=f[1][n];
for(j=1;j<=n;++j)
{
if (f[j][n]<tmp)
tmp=f[j][n];
}//end for
cout <<tmp<<endl;
system("pause");
return 0;
}//end main
挺好玩的一道題。。。
NOIP2006的第一題。
在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并
且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過(guò)吸盤(pán)（吸盤(pán)是Mars人吸收能量的一種器官）的作用，這兩顆
珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤(pán)吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后
釋放的能量為m*r*n（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。
需要時(shí)，Mars人就用吸盤(pán)夾住相鄰的兩顆珠子，通過(guò)聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。
例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號(hào)⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【輸入文件】
輸入文件energy.in的第一行是一個(gè)正整數(shù)N（4≤N≤100），表示項(xiàng)鏈上珠子的個(gè)數(shù)。第二行是N個(gè)用空格隔開(kāi)的正整數(shù)，所有的數(shù)均不超過(guò)
1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記（1≤i≤N），當(dāng)i<N<
span>時(shí)，第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。
至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針?lè)较虼_定其他珠子的順序。
【輸出文件】
輸出文件energy.out只有一行，是一個(gè)正整數(shù)E（E≤2.1*109），為一個(gè)最優(yōu)聚合順序所釋放的總能量。
【輸入樣例】
4
2 3 5 10
【輸出樣例】
710
#include <iostream>
using namespace std;
#define MAX 100
int n;//數(shù)量
int f[MAX][MAX];
int a[MAX];//a[i]為第i個(gè)珠子的值
int k,i,j,r,tmp;
int max(int x,int y)
{
if (x>y) return x;
return y;
}
int main()
{
cin >>n;
for (i=0;i<n;++i)
{
cin >>a[i];
}
for(i=2;i<=n;i++)
for(j=0;j<n;j++)
{
k=(i+j)%n;
for(r=1;r<i;r++)
f[j][k]=max(f[j][(j+r)%n]+f[(j+r)%n][k]+a[j]*a[(j+r)%n]*a[k],f[j][k]);
}
tmp=-1;
for(i=0;i<n;i++)
if(f[i][i]>tmp)tmp=f[i][i];
cout<<tmp<<endl;
system("pause");
return 0;
}