Warmup for 2011 Asia Regional Chengdu

1004 Discount
問題に穴をあけられて、いつも割引に連想します.後で前の問題とは関係ないことに気づいた.
n個の数を与えて、1からこのn個の数の中である数の和の最小値がどれだけあるかを聞く.
まずn個の数の前に1つの0を補って並べ替え、その後その接頭辞とsumを求める、sum[i-1]+1がa[i]より小さいか否かを判断し、もし小さいならansがsum[i-1]+1である.
簡単な帰納証明:
iが1に等しい場合、sum[0]=0,a[1]!=1の場合、必ず1の場合は発生しません.
i>=2の場合、i-1が上記の判断に対して成立すると仮定すると、すなわち、1からsum[i-1]までが前i-1の数で表され、sum[i-1]+1>=a[i]の場合、すべての1からsum[i-1]+a[i](すなわちsum[i])が求めることができる(sum[i-1]からsum[i]までの間がa[i]に加算された前に現れる数であることを検証するだけでよい)

#include <cstdio>
#include <cstring>
#include <algorithm>
#define min(a,b) a>b?b:a;

using namespace std;
const int maxn=1005;

int sum[maxn];
int a[maxn];
int main ()
{
    int n;
    while (~scanf("%d",&n))
    {
        a[0]=sum[0]=0;
        for (int i=1 ; i<=n ; ++i)
        {
            scanf("%d",a+i);
            sum[i]=sum[i-1]+a[i];
        }
        sort(a,a+n+1);
        int ans=sum[n]+1;
        for (int i=0 ; i<n ; ++i)
        {
            if(sum[i]+1<a[i+1])
            ans=min(sum[i]+1,ans);
        }
        printf("%d
",ans);
    }
    return 0;
}

 
1005
簡単DP、状態が良いDP[i][j][1,0]は、現在処理されているiを起点とするjを終点とし、状態が1-ピーク0-谷の最も多いスペース数であることを示し、
境界条件はdp[0][i][0]=0である.すなわち,0を起点とするすべての状態がピーク谷のスペース数である.
 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=105;

int num[maxn][maxn];// i   ，j     
int dp[maxn][maxn][2];// i  ，j   ，1-- ，0-- ；
int n;
char str[maxn];

void DP()
{
    memset (dp, -1, sizeof(dp));
    for (int i=0 ; i<n ; ++i)
    {
        for (int j=i ; j<n ; ++j)
        {
            if(i==0)
            dp[i][j][0]=0;
            //1
            for (int k=0 ; k<i ; ++k)
            {
                if(num[i][j]>num[k][i-1])
                {
                    dp[i][j][1]=max(dp[i][j][1], dp[k][i-1][0]+1);
                }
            //0
                if(num[i][j]<num[k][i-1])
                {
                    dp[i][j][0]=max(dp[i][j][0], dp[k][i-1][1]+1);
                }
            }
        }
    }
    int ans=0;
    for (int i=0 ; i<n ; ++i)
    {
        ans=max(ans, dp[i][n-1][1]);
        ans=max(ans, dp[i][n-1][0]);
    }
    printf("%d
",ans);
}

int main ()
{
    while (~scanf("%d%s",&n,str))
    {
        for (int i=0 ; i<n ; ++i)
        {
            num[i][i]=str[i]-'0';
            for (int j=i+1 ; j<n ; ++j)
            {
                num[i][j]=num[i][j-1]*10+str[j]-'0';
            }
        }
        DP();
    }
    return 0;
}

 
 
1009 Instrction Arrangement
メモリ検索または最長パス

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
struct Edge {
	int v,next,w;
}edge[100000+123];

int head[1005],cnt;
int dis[1005];
int deg[1005];
void addedge(int u, int v, int w)
{
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
	cnt++;
}

void init ()
{
	cnt=0;
	memset (head, -1 , sizeof(head));
	memset (dis, -1, sizeof(dis));
	memset (deg, 0, sizeof(deg));
}

void dfs (int f)
{
    int p=head[f];
    if(~dis[f])return;
    int ans=0;
    for ( ; ~p ; p=edge[p].next)
    {
        dfs(edge[p].v);
        ans=max(dis[edge[p].v]+edge[p].w, ans);
    }
    dis[f]=ans;
}

int main ()
{
	int n,m;
	int a,b,c;
	while (~scanf("%d%d", &n, &m))
	{
		init();
		for (int i=0 ; i<m ; ++i)
		{
			scanf("%d%d%d", &a, &b, &c);
			++deg[b];
			addedge(a,b,c);
		}
		/*
		for (int i=0 ; i<n ; ++i)
		{
		    for (int j=head[i]; ~j ; j=edge[j].next)
		    {
		        printf("%d %d 
", i, edge[j].v);
		    }
		}*/
		for (int i=0 ; i<n ; ++i)
		{
		    //printf("deg==%d
", deg[i]);
			if(!deg[i])addedge(n, i, 0);
		}

		dfs(n);
		int ans=0;
		for (int i=0 ; i<n ; ++i)
		{
		    //printf("dis==%d
", dis[i]);
			ans=max(ans, dis[i]);
		}
		printf("%d
",ans+1);
	}
	return 0;
}