作业代码

作业代码

//3.3  path 路径
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
struct node
{
	int v, a, b, c[2000];
}p[50][50];
int mmin(int a,int b)
{
	if (a > b) return b;
	else return a;
}
int fac(int x)
{  return x*x;  }
int main()
{
	int T, o = 0;
	cin >> T;
	while (T--)
	{
		int n, m;
		cin >> n >> m;
		memset(p, 0, sizeof(p));
		for (int i0 = 1;i0 <= n;i0++)
			for (int j = 1;j <= m;j++)
				cin >> p[i0][j].v;
		p[1][1].a = fac(p[1][1].v);
		p[1][1].b = p[1][1].v; 
		p[1][1].c[p[1][1].v] = fac(p[1][1].v); 
		for (int j = 2;j <= m;j++)
		{
			p[1][j].a = p[1][j - 1].a + fac(p[1][j].v);
			p[1][j].b = p[1][j - 1].b + p[1][j].v;
			p[1][j].c[p[1][j].b] = p[1][j].a;
		}
		for (int i1 = 2;i1 <= n;i1++)
		{
			p[i1][1].a = p[i1 - 1][1].a + fac(p[i1][1].v);
			p[i1][1].b = p[i1 - 1][1].b + p[i1][1].v;
			p[i1][1].c[p[i1][1].b] = p[i1][1].a;
		}
		for (int i = 2;i <= n;i++)
			for (int j = 2;j <= m;j++)
				for (int k = 0;k < 2000;k++) 
				{
					if (p[i][j - 1].c[k])
					{
						int f = k + p[i][j].v;
						if (p[i][j].c[f])                       
							p[i][j].c[f] = mmin(  p[i][j].c[f], p[i][j - 1].c[k] + fac(p[i][j].v)  );
						else
							p[i][j].c[f] = p[i][j - 1].c[k] + fac(p[i][j].v);
					}
					if (p[i - 1][j].c[k])
					{
						int f = k + p[i][j].v;
						if (p[i][j].c[f])
							p[i][j].c[f] = mmin(p[i][j].c[f], p[i - 1][j].c[k] + fac(p[i][j].v));
                        else
							p[i][j].c[f] = p[i - 1][j].c[k] + fac(p[i][j].v);
					}
				}
		int ans = 1000000000;
		for (int i2 = 0;i2 < 2000;i2++)
			if (p[n][m].c[i2])
				ans = mmin(ans, (n + m - 1)*p[n][m].c[i2] - fac(i2));
		printf("Case #%d: %d
", ++o, ans);
	}
	return 0;
}

//4.4 szjl 数字接力
#include<cstdio>   
#include<cstring>   
#include<iostream>   
using namespace std;   
char a[1005][32];   
char p[1005][32];     
int n = 0;   
//自己写一个字符串比较函数   
int strcmp_vv(char s[], char t[])   
{   
    char r[200];   
    char r1[200];   
    strcpy(r, s);   
    strcat(r, t);   
    strcpy(r1, t);   
    strcat(r1, s);   
    int i = strcmp(r, r1);   
    return i;   
}   
  
void outv()   
{     
    for (int i = 0;i < n;i++)     
        printf("%s",a[i]);             
    printf("
");   
}   
  
//将有二个有序数列a[first...mid]和a[mid...last]合并。     
void mergearray(char a[][32], int first, int mid, int last,char temp[][32])   
{     
    int i = first, j = mid + 1;   
    int m = mid, n = last;   
    int k = 0;   
    while (i <= m && j <= n)   
    { 
        if (strcmp_vv(a[i], a[j])==1)     
            strcpy(temp[k++], a[i++]);     
        else     
            strcpy(temp[k++], a[j++]);   
    }   
    while (i <= m)   
        strcpy(temp[k++] , a[i++]);   
    while (j <= n)   
        strcpy(temp[k++] , a[j++]);   
    for (i = 0; i < k; i++)   
        strcpy(a[first + i] , temp[i]); 
	cout<<" first "<<first<<" mid "<<mid<<" last "<<last<<endl;
    outv();  	
    cout<<endl;
}   
void mergesort(char a[][32], int first, int last,char temp[][32])   
{   
    if (first < last)   
    {    
        int mid = (first + last) / 2;   
        mergesort(a, first, mid,temp);    
        mergesort(a, mid + 1, last,temp);    
        mergearray(a, first, mid, last,temp);     
    }    
}   
bool MergeSort(char a[][32], int n)   
{   
    if (p == NULL) return false;   
    mergesort(a, 0, n - 1,p);   
    return true;   
}   
int main()   
{   
    cin >> n;   
    for (int i = 0;i < n;i++)    cin >> a[i];    
    MergeSort(a,n);   
    outv();   
    return 0;   
}