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是荷蘭人寫的，Ruby是日本人寫的，Lua是巴西人寫的，我這個中國人只能在這里臉紅。
——CSDN主編 孟巖
不打算自討沒趣地寫個要超過Python,Ruby,Lua的腳本引擎，以鍛煉能力為主。
估計完成以后和Lua有點像，宗旨是：以比Lua更短為榮，以比Python更長為恥 :-)
┏━┓ ┏━━┓ ┏┓
┃┃┣━┳━┫━━╋━┳┳╋╋━┳━━┓
┃ ┫━┃┃┣━━┃┣┫┏┫┃┃┣┓┏┛
┗┻┻┻┫┏┻━━┻━┻┛┗┫┏┛┗┛
┗┛ ┗┛
引擎就叫RapScript好了(Ruby,Lua,Python 加一起)
附上題目：
在一個圓形操場的四周擺放著n堆石子。現要將石子有次序地合并成一堆。規定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數記為該次合并的得分。試設計一個算法，計算出將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;//循環用的
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星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數。并
且，對于相鄰的兩顆珠子，前一顆珠子的尾標記一定等于后一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆
珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為m，尾標記為r，后一顆能量珠的頭標記為r，尾標記為n，則聚合后
釋放的能量為m*r*n（Mars單位），新產生的珠子的頭標記為m，尾標記為n。
需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。
例如：設N=4，4顆珠子的頭標記與尾標記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項鏈可以得到最優值的一個聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【輸入文件】
輸入文件energy.in的第一行是一個正整數N（4≤N≤100），表示項鏈上珠子的個數。第二行是N個用空格隔開的正整數，所有的數均不超過
1000。第i個數為第i顆珠子的頭標記（1≤i≤N），當i<N<
span>時，第i顆珠子的尾標記應該等于第i+1顆珠子的頭標記。第N顆珠子的尾標記應該等于第1顆珠子的頭標記。
至于珠子的順序，你可以這樣確定：將項鏈放到桌面上，不要出現交叉，隨意指定第一顆珠子，然后按順時針方向確定其他珠子的順序。
【輸出文件】
輸出文件energy.out只有一行，是一個正整數E（E≤2.1*109），為一個最優聚合順序所釋放的總能量。
【輸入樣例】
4
2 3 5 10
【輸出樣例】
710
#include <iostream>
using namespace std;
#define MAX 100
int n;//數量
int f[MAX][MAX];
int a[MAX];//a[i]為第i個珠子的值
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;
}