切割钢条

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n=10,p[100]={0,1,5,8,9,10,17,17,20,24,24},c[100],summax,rec[100];
int main(){
//	cin>>n;
//	for(int i=1;i<=n;i++)cin>>p[i];
	for(int i=1;i<=n;i++){
		summax=p[i];
		rec[i]=i;
		for(int j=1;j<i;j++){
			if(c[j]+c[i-j]>summax){
				summax=c[j]+c[i-j];
				rec[i]=j;
			}
		}
		c[i]=summax;
	}
	cout<<c[n]<<endl;
	while(n>0){
		cout<<rec[n]<<" ";
		n-=rec[n];
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
char x[N],y[N];
int c[N][N],rec[N][N];

void lcs(int i,int j){
	if(i==0||j==0){
		return;
	}
	if(rec[i][j]==1){
		cout<<rec[i][j]<<" "<<i<<" "<<j<<endl;
		lcs(i-1,j-1);
		cout<<x[i-1]<<" ";
	}else if(rec[i][j]==2){
		lcs(i-1,j);
	}else{
		lcs(i,j-1);
	}
}

int main(){
	cin>>x>>y;
	int n,m;
	n=strlen(x);
	m=strlen(y);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(x[i-1]==y[j-1]){
				c[i][j]=c[i-1][j-1]+1;
				rec[i][j]=1;
			}else if(c[i-1][j]>c[i][j-1]){
				c[i][j]=c[i-1][j];
				rec[i][j]=2;
			}else{
				c[i][j]=c[i][j-1];
				rec[i][j]=3;
			}
		}
	}
	cout<<c[n][m]<<endl;
	lcs(n,m);
	return 0;
}