bestcoder#63 div1

第一次做div1,解出两道题,能做的也只有两道。但是第一题罚时有点厉害,一直不太相信需要高精度(因为output里写了integer。。)
1001(hdu5568) sequence2
一个整数序列有多少种长度为k的不同的递增子序列,两个子序列只要有一个元素对应位置不同就算不同。
如1 2 2有两个长度为2的不同子序列1 2和1 2(这两个2位置不同)
简单的dp题。dp[i][j]表示前i个数组成的序列中有多少个长度为j的不同子序列。
dp[i][j]=sigma(dp[t][j-1]),其中a[i]>a[t]。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
};
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}

int n,k;
BigNum dp[110][110];
int a[110];
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++) dp[i][1]=1;
        for(j=2;j<=k;j++)
            for(i=1;i<=n;i++)
                for(t=1;t<=i-1;t++)
                    if(a[i]>a[t]) dp[i][j]=dp[i][j]+dp[t][j-1];
        BigNum ans=0;
        for(i=1;i<=n;i++) ans=ans+dp[i][k];
        cout<<ans<<endl;


    }
    return 0;
}

1002(hdu5569) matrix
也是比较简单的dp题,转移方程容易想到,具体见代码。

#include<stdio.h>
#include<string.h>
typedef long long ll;
int n,m;
int a[1010][1010];
int dp[1010][1010];
const int inf=0x3f3f3f3f;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;

}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                dp[i][j]=0;
            }
        dp[1][2]=a[1][1]*a[1][2];
        dp[2][1]=a[1][1]*a[2][1];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i==1) && (j==2)) continue;
                if((i==2) && (j==1)) continue;
                if((i+j)%2==0) continue;
                int tmp1=-1,tmp2=-1,tmp=0;
                if(judge(i,j-1))
                {
                    tmp1=a[i][j]*a[i][j-1];
                    tmp=inf;
                    if(judge(i,j-2)) tmp=dp[i][j-2];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp1+=tmp;
                }
                if(judge(i-1,j))
                {
                    tmp2=a[i][j]*a[i-1][j];
                    tmp=inf;
                    if(judge(i-2,j)) tmp=dp[i-2][j];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp2+=tmp;
                }
                if((tmp1==-1) || (tmp2==-1)) dp[i][j]=max(tmp1,tmp2);
                else dp[i][j]=min(tmp1,tmp2);
            }
        printf("%d\n",dp[n][m]);

    }


    return 0;
}

1003 balls
做不出来,看了题解还没完全清楚。。