Code: Select all
cost(start, end)=min(cost(start,k)+cost(k,end)+(end-start))Code: Select all
#include <stdio.h>
#include <limits.h>
int table[100][100]={0};
int profit[100][100]={0};
int data[100];
int n;
int len;
void process(){
int i,j,k,min=INT_MAX;
for(i=n-1;i>=1;i--)
for(j=i+1;j<=n;j++){
min=INT_MAX;
for(k=1;k<=j-i;k++){
if( table[i][j-k]+table[j+1-k][j]<min )
min=table[i][j-k]+table[j+1-k][j];
}
table[i][j]=min;
}
}
void profit_process(){
int i,j,k,min=INT_MAX;
for(i=n-1;i>=1;i--)
for(j=i+1;j<=n;j++){
min=INT_MAX;
for(k=1;k<=j-i;k++){
if( i==j-k && j+1-k==j ){
if( table[i][j-k]+table[j+1-k][j]<min )
min=table[i][j-k]+table[j+1-k][j];
}else{
if( i==j-k ){
if( profit[j+1-k][j]+table[i][j]<min )
min=profit[j+1-k][j]+table[i][j];
}else if( j+1-k==j ){
if( profit[i][j-k]+table[i][j]<min )
min=profit[i][j-k]+table[i][j];
}else{
if( profit[i][j-k]+profit[j+1-k][j]+table[i][j]<min )
min=profit[i][j-k]+profit[j+1-k][j]+table[i][j];
}
}
}
profit[i][j]=min;
}
printf("The minimum cutting is %d.\n",profit[1][n]);
}
int main(){
int i,pre,temp;
while( scanf("%d",&len)==1 && len ){
scanf("%d",&n);
n=n+1;
pre=0;
for(i=1;i<n;i++){
scanf("%d",&temp);
profit[i][i]=table[i][i]=temp-pre;
pre=temp;
}
profit[i][i]=table[i][i]=len-pre;
process();
profit_process();
}
return 0;
}Code: Select all
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int a[1001];
int data[1001][1001];
class sumant
{
public:
int count;
int input()
{
int l,x,n;
cin>>l;
while(l!=0)
{
count=0;
for(int i=0;i<=l;i++)
for(int j=0;j<=l;j++)
data[i][j]=-1;
cin>>n;
for(int i=0;i<=l;i++)
a[i]=0;
for(int i=0;i<n;i++)
{
cin>>x;
a[x]=1;
}
int z=memo(0,l);
cout<<"The minimum cutting is "<<z<<".\n";
//cout<<count<<"\n";
cin>>l;
}
}
int memo(int p,int q)
{
if(data[p][q]==-1)
{
int z=doit(p,q);
data[p][q]=z;
return z;
}
else
{
return data[p][q];
}
}
int doit(int p,int q)
{
int min=100000000,m;
bool flag=false;
for(int i=p+1;i<q;i++)
{
if(a[i]!=0)
{
flag=true;break;
}
}
if(!flag)
return 0;
for(int i=p+1;i<q;i++)
{
if(a[i]==1)
{
//cout<<"madar";
m=q-p+memo(p,i)+memo(i,q);
if(min>m)
min=m;
flag=true;
}
}
return min;
}
};
int main()
{
sumant s;
s.input();
return 0;
}
Code: Select all
int a[1001];
int data[1001][1001];
Code: Select all
int a[51];
int data[51][51];
Code: Select all
I got accepted thanks to the help of emotional blind.
Code: Select all
memset(cache, -1, sizeof(cache));Code: Select all
for(int i=0;i<=n+1;++i){
for(int j=i;j<=n+1;++j){
cache[p[i]][p[j]]=-1;
}
}Code: Select all
for (int i=1; i<=n; ++i){
cin >> p[i];
} Code: Select all
#include<iostream>
using namespace std;
#define INF 4294967295
int num,l;
int length;
bool cut[100000];
unsigned long s[2005][2005] = {0};
// will print the ordering of cutting
//this part is optional to UVA 10003 problem
void print(int i,int j)
{
if( s[i][j] != 0)
printf("%d ",s[i][j]);
else return;
print(i,s[i][j]);
print(s[i][j],j);
}
void matrix_chain()
{
unsigned long m[500][500] = {0};
//int **m;
unsigned int q;
int l,j,i,k;
int check = 0;
memset(s,0,sizeof(s));
//memset(m,0,sizeof(m));
for( l = 2; l <= length; l++)
{
for( i = 0; i <= length-l; i++)
{
j = i+l;
m[i][j] = INF;
for( k = i + 1; k < j;k++)
{
if( cut[k] == true )
{
check = 1;
q = m[i][k] + m[k][j] + (j - i);
if( q < m[i][j])
{
m[i][j] = q;
s[i][j] = k;
}
}
}
if( check == 0)
{
m[i][j] = 0;
}
check = 0;
}
}
cout << m[0][length] << ".\n" ;
print(0,length);
cout << endl;
}
int main(void)
{
int size,i,k,m,n,c = 1;
int p[2010] = {0};
while(1)
{
cin >> l;
length = l;
if(!l) break;
cin >> n;
memset(cut,false,sizeof(cut));
for(i = 1; i <= n; i++)
{
cin >> m;
cut[m] = true;
}
cout << "The minimum cutting is ";
matrix_chain();
}
return 0;
}
