发表于 | 分类于 | 阅读次数:

题意分析：

题目意思是在邻接矩阵中判断图的连通性,不解释

用的Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <stdlib.h>
#include <strin
int main()
{
    freopen("Sample Input.txt","r",stdin);
    system("Color F0");
    char s[100];
    int i,j,k,len;
    int m[30][30];
    while (gets(s))
    {
        memset(m,0,sizeof(m));
        while (s[0]!='0')
        {
            len = strlen(s);
            m[s[0]-'a'][s[len-1]-'a'] = 1;
            gets(s);
        }
        for ( k = 0; k < 26; k++)
        {
            for ( i = 0; i < 26; i++)
            {
                if (i==k)
                    continue;
                for ( j = 0; j < 26; j++)
                {
                    if ( j==k || j==i )
                        continue;
                    if ( m[i][k] && m[k][j] ) m[i][j] = 1;
                }
            }
        
        if (m[1][12])
            printf("Yes.\n");
        else
            printf("No.\n");
    }
    getch();
    return 0;

发表于 | 分类于 | 阅读次数:

搜索题，这题就是数据量大，其他没什么，BFS时记录转折就好了

用BFS做的，10000MS TLE了N次直接亮瞎。。。

最后面发现BFS四个方向的顺序也有关系（改下就AC了）

TLE时：

1
2
int iPlus[4] = {-1,0,0,1};
int jPlus[4] = {0,-1,1,0};

改成下面的就AC了：

1
2
int iPlus[4] = {-1,0,1,0};
int jPlus[4] = {0,-1,0,1};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 1000000
const int  INF = 999999;
typedef struct
{
    int x;
    int y;
    int dir;
    int num;
}point;

struct Queue
{
    point base[SIZE];
    int front,rear;
}Q;

void init() {Q.rear = Q.front = 0;}

void Push(point e)
{
    Q.base[Q.rear].x = e.x;
    Q.base[Q.rear].y = e.y;
    Q.base[Q.rear].dir = e.dir;
    Q.base[Q.rear].num = e.num;
    Q.rear = (Q.rear+1)%SIZE;
}

point Pop()
{
    point e;
    e.x = Q.base[Q.front].x;
    e.y = Q.base[Q.front].y;
    e.dir = Q.base[Q.front].dir;
    e.num = Q.base[Q.front].num;
    Q.front = (Q.front+1)%SIZE;
    return e;
}

int n,m,q;
int map[1010][1010];
int mark[1010][1010];
int iPlus[4] = {-1,0,1,0};
int jPlus[4] = {0,-1,0,1};

void BFS(point p1,point p2)
{
    int k;
    point next,pre;
    init();
    pre.x = p1.x;pre.y = p1.y;
    pre.num = 0;
    pre.dir = -1;
    Push(pre);
    mark[p1.x][p1.y] = 0;
    while (Q.rear!=Q.front)
    {
        pre = Pop();
        for ( k = 0; k < 4; k++)
        {
            next.x = pre.x + iPlus[k];
            next.y = pre.y + jPlus[k];
            if (next.x < 1 || next.y < 1 || next.x > n || next.y > m)
                continue;
            if (pre.dir == -1 )
                next.num = 0;
            else
            {
                if ( k != pre.dir )
                    next.num = pre.num + 1;
                else
                    next.num = pre.num;
            }
            next.dir = k;
            if ( next.x == p2.x && next.y==p2.y && next.num <= 2 )
            {
                printf("YES\n");
                    return;
            }
            if ( map[next.x][next.y] == 0 && next.num <= mark[next.x][next.y] )
            {
                mark[next.x][next.y] = next.num;
                Push(next);
            }
        }
    }
    printf("NO\n");
}

int main()
{
    freopen("Sample Input.txt","r",stdin);
    system("Color F0");
    int i,j,k;
    point p1,p2;
    while ( scanf("%d%d",&n,&m),n&&m)
    {
        for ( i = 1; i <= n; i++)
        for ( j = 1; j <= m; j++)
        scanf("%d",&map[i][j]);
        scanf("%d",&q);
        while (q--)
        {
            scanf("%d%d%d%d",&p1.x,&p1.y,&p2.x,&p2.y);
            for ( i = 1; i <= n; i++)
                for ( j = 1; j <= m ; j++)
                    mark[i][j] = INF;
            if (map[p1.x][p1.y]==0 || map[p2.x][p2.y]==0 || map[p1.x][p1.y] != map[p2.x][p2.y] )
            {
                printf("NO\n");
                continue;
            }
            if (p1.x < 1 || p1.y < 1 || p1.x > n || p1.y > m || p2.x < 1 || p2.y < 1 || p2.x > n || p2.y > m)
            {
                printf("NO\n");
                continue;
            }
            BFS(p1,p2);
        }
    }
    getch();
    return 0;
}

发表于 | 分类于 | 阅读次数:

起初以为这题是用Floyd算法，便起手尝试着做，Floyd的路径保存和输出又不懂，结果一直WA。。

后面才知道原来只要简单的DP就可以求出最长（兴趣点最高）路径，需要注意的还是路径的输出，DP时用pre[x]保存访问顶点x时的前驱，这样就OK了。

1
2
if(map[j][i]!=-1&&dp[j] + map[j][i] > dp[i]) //状态转移要判断从j到i是否可以走通
    dp[i] = dp[j] + map[j][i];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(a,b) (a)>(b)?(a):(b)
int map[110][110];
int dp[110];
int pre[110];
int inst[110];
void output( int x )
{
    if ( x == -1)
        return;
    output(pre[x]);
    printf("%d->",x);
}
int main()
{
    int T,n,m;
    int i,j,k;
    int cases = 1;
    scanf("%d",&T);
    while ( T-- )
    {
        scanf("%d",&n);
        for ( i = 1; i <= n+1; i++)
            for( j = 1; j <= n+1; j++)
                map[i][j] = -1;
        memset(dp,0,sizeof(dp));
        for ( i = 1; i <= n; i++)
            scanf("%d",&inst[i]);
        inst[n+1] = 0;
        scanf("%d",&m);
        for ( k = 1; k <= m; k++)
        {
            scanf("%d%d",&i,&j);
            map[i][j] = inst[j];
        }
        pre[1] = -1;
        for ( i = 1; i <= n + 1; i++)
            for ( j = 1; j < i; j++)
            {
                if(map[j][i]!=-1&& dp[j] + map[j][i] > dp[i] )
                {
                    dp[i] = dp[j] + map[j][i];
                    pre[i] = j;
                }
            }
        if ( cases>1 )printf("\n");
        printf("CASE %d#\n",cases++);
        printf("points : %d\n",dp[n+1]);
        printf("circuit : ");
        output(pre[n+1]);
        printf("1\n");
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

二维完全背包吧，我的思路是这样的：

minp[i][j]
表示玩家杀死j只怪物取得经验值i 减少的最小疲劳度

状态转移方程： minp[i][j] =
MIN(minp[i][j],minp[i-monsters[k].Exp][j-1]+monsters[k].T)

这边需要注意的问题： 初始状态只有minp[0][0]=0 其他为一个无穷大的数，这边也可以定义INF为200

特别要注意的情况是可以杀死怪物取得经验值i大于升级所需的经验LiftUp，此时有可能牺牲的疲劳度是较小的（一开始考虑成每次升级都是获得刚好的经验值WA了几次）是较优的，所有i的变化范围应该是从monsters[k].Exp 到 LiftUp+monsters[k].Exp

每次状态转移后要增加判定条件

1
2
if ( i> LiftUp && minp[LiftUp][j] >___minp[i][j])  
    minp[LiftUp][j] = minp[i][j];

最后从 minp[LiftUp][j] ( 1<= j <= 最多杀怪数) 找出最小值就是升级所需要的最小疲劳度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>
#define INF 200
#define MIN(x,y) (x)<(y)?(x):(y)
#define MAX(x,y) (x)>(y)?(x):(y)
struct node
{
    int Exp;
    int T;
}monsters[105];
int minp[205][205];
//minp[i][j] Is the minimal power cost when player kill j monsters and acquire experiences: i
int main()
{
    //freopen("Sample Input.txt","r",stdin);
    intLiftUp,power,n,mkill;
    int i,j,k;
    int m;
    while ( scanf("%d%d%d%d",&LiftUp,&power,&n,&mkill)!=EOF)
    {
        for ( i = 1; i <= n; i++)
            scanf("%d%d",&monsters[i].Exp,&monsters[i].T);
        for ( i = 0; i <= 200; i++)
            for ( j = 0; j<= 100; j++)
                minp[i][j] = INF;
        minp[0][0] = 0;
        for ( k = 1; k <= n; k++)
        {
            for ( j = 1; j<=mkill; j++)
                for ( i = monsters[k].Exp; i < LiftUp+monsters[k].Exp; i++)
                {
                    minp[i][j] = MIN(minp[i][j],minp[i-monsters[k].Exp][j-1]+monsters[k].
                        //Note: In some cases the best way is the experience over the LiftUp experience the cost is lowest !
                        // So Use minp[LiftUp][j] to replace minp[i][j],when i greater than LiftUp, and mi][j] costs a lower po
                    if ( i> LiftUp && minp[LiftUp][j] > minp[i][j])
                        minp[LiftUp][j] = minp[i][j] ;
                }
        }
        for ( m = INF,j = 0; j <= mkill; j++)
            m = MIN(m,minp[LiftUp][j]);
        if (power-m>=0)
            printf("%d\n",power-m);
        else
            printf("-1\n");
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

思路：

depots[i][j] 表示i个供应站j个饭馆的最优值

cost[i][j] 表示 从i到j建立一个供应站后的耗费（可以得知供应站必定建在中位数处:下标为(i+j)/2）

状态方程：

depots[i][j] = MIN(depots[i][j],depots[i-1][m]+cost[m+1][j])

在m处建立i-1个供应站，在m到j处建立一个供应站，找出最小值

这边m的范围要注意 i-1<=m<j 建立一个供应站先确定depots的初始条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define inf 0x7fffffff
#define MIN(x,y) (x)<(y)?(x):(y)
int distance[220];
int depots[35][220];
int cost[220][220];
int main()
{
    int n,k,m,p;
    int i,j;
    int cases = 1;
    freopen("Sample Input.txt","r",stdin);
    while ( scanf("%d%d",&n,&k),n||k)
    {
        for ( i = 1; i <= n; i++)
            scanf("%d",&distance[i]);
        for ( i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                cost[i][j] = 0;
                for ( p = i; p <= j; p++)
                    cost[i][j] += abs(distance[p] - distance[(i+j)/2]);
            }
        }
        for ( i = 1; i <= n; i++)
            depots[1][i] = cost[1][i];
        for ( i = 2; i <= k; i++)
        {
            for (j = i + 1; j <= n; j++)  
            {
                depots[i][j] = inf;
                for ( m = i - 1; m < j; m++)
                    depots[i][j] = MIN(depots[i][j],depots[i-1][m] + cost[m+1][j]);
            }
        }
        printf("Chain %d\n",cases++);
        printf("Total distance sum = %d\n\n",depots[k][n]);
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

（其实还是用LCS的方法就可以了，考虑了好久，起初在数据输入地方就搞错了 T_T）

Max_Score[i][j]: 当第i颗子弹对付第j个恐怖分子的最大得分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(x,y) (x)>(y)?(x):(y)
int MaxScore[2005][2005];
char Kind[150],TE[2005],Kill[2005];
int Score[150];
int main()
{
    //freopen("Sample Input.txt","r",stdin);
    int i,N,j;
    int tmp;
    int TLen,KLen;
    while (scanf("%d",&N)!=EOF)
    {
        getchar();
        for ( i = 0; i < N; i++)
            scanf("%c",&Kind[i]);
        getchar();
        for ( i = 0; i < N; i++)
        {
            scanf("%d",&tmp);
            Score[Kind[i]] = tmp;
        }
        getchar();
        scanf("%s%s",Kill,TE);
        KLen = strlen(Kill); TLen = strlen(TE);
        for ( i = 0; i <= KLen; i++)
            MaxScore[i][0] = 0;
        for ( j = 0; j <= TLen; j++)
            MaxScore[0][j] = 0;
        for ( i = 1; i <= KLen; i++)
        {
            for ( j = 1; j <= TLen; j++)
            {
                if ( Kill[i-1]==TE[j-1] )
                    MaxScore[i][j] = MaxScore[i-1][j-1] + Score[TE[j-1]];
                else
                    MaxScore[i][j] = MAX(MaxScore[i-1][j],MaxScore[i][j-1]);
            }
        }
        printf("%d\n",MaxScore[KLen][TLen]);
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

背包问题，考虑是先计算出总量的一半，然后判断能否把这个背包装满。

觉得这题自己有点乱搞，虽然用下面的算法把它AC了，可能是数据太弱了，觉得这个算法还是有点问题。

PE了一次，原来是每组数据后都要一个n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int w[7] = {0};
int knap(int T,int p)
{
    if ( p < 1) return 0;
    if (!T) return 1;
    //找出当前可以放下的最大的那个
    while (w[p] == 0 || p > T) p--;  
    w[p]--;
    //做二分选择放入背包和不放入背包
    return ( knap(T-p,p) || knap(T,p-1));
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int cse;
    int i,Flag;
    int HalfSpace;
    cse = 1;
    while ( scanf("%d%d%d%d%d%d",&w[1],&w[2],&w[3],&w[4],&w[5],&w[6]),w[1]||w[2]||w[3]||w[4]||w[5]||w[6])
    {
        HalfSpace = 0;
        for ( i = 1; i <= 6; i++)
            HalfSpace += w[i]*i;
        if ( HalfSpace%2 )  Flag = 0;
        else
        {
            HalfSpace/=2;
            Flag = knap(HalfSpace,6);
        }
        printf("Collection #%d:\n",cse++);
        if ( Flag )
            printf("Can be divided.\n\n");
        else
            printf("Can't be divided.\n\n");
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

完全背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF  1000000000
#define MIN(x,y) (x)<(y)?(x):(y)
#define MAX(x,y) (x)>(y)?(x):(y)
typedef struct CoinType
{
    int P;
    int W;
}CoinType;
CoinType coin[1000];
int Min[20000];
int E,F,N,Piggy_Bank;
int main()
{
    int i,j,T;
    scanf("%d",&T);
    while ( T--)
    {
        scanf("%d%d",&E,&F);
        Piggy_Bank = F - E;
        scanf("%d",&N);
        for ( i = 0; i < N; i++)
            scanf("%d%d",&coin[i].P,&coin[i].W);
        Min[0] = 0;
        for ( i = 1; i <= Piggy_Bank; i++) Min[i] = INF;
        for ( i = 0; i < N; i++)
        {
            for ( j = coin[i].W; j <= Piggy_Bank; j++)
                Min[j] =  MIN(Min[j-coin[i].W]+coin[i].P,Min[j]);
        }
        if ( Min[Piggy_Bank] < INF)
            printf("The minimum amount of money in the piggy-bank is %d.\n",Min[Piggy_Bank]);
        else
            printf("This is impossible.\n");
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

经典DP题目，就是求最长上升子序列的和！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(x,y) (x)>(y)?(x):(y)
__int64 max[1200];
__int64 a[1200];
int main()
{
    int n,i,j;
    __int64 temp;
    while (scanf("%d",&n),n)
    {
        memset(max,0,sizeof(max));
        for ( i = 0; i < n;i++)
        {
            scanf("%I64d",&a[i]);
            temp = a[i];
            for ( j = 0;j < i;j++)
                if ( a[j] < a[i] )
                    temp = max(temp,max[j]+a[i]);
            max[i] = temp;
        }
        temp = 0;
        for ( j = 0; j < n; j++)
            temp = max(max[j],temp);
        printf("%I64d\n",temp);
    }
    return 0;  
}

发表于 | 分类于 | 阅读次数: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(x,y) (x)<(y)?(x):(y)
#define INF 0x7fffffff
int dp[2000][1000];
int w[2000];
int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
int main()
{
    int n,k;
    int i,j;
    while (scanf("%d%d",&n,&k)!=EOF)
    {
        for ( i = 1; i <= n;i++)
            scanf("%d",&w[i]);
        qsort(w+1,n,sizeof(w[1]),cmp);
        for ( i = 0; i <= n; i++)
        {
            dp[i][0] = 0;
            for ( j = 1; j<=k; j++)
                dp[i][j] = INF;
        }
        for ( i = 2; i <= n; i++)
        {
            for (j = 1; j <= i/2 ;j++)  
                dp[i][j] = min(dp[i-1][j],dp[i-2][j-1] + (w[i]-w[i-1])*(w[i]-w[i-1]));
        }
        //状态方程：dp[i][j] = min(dp[i-1][j],dp[i-2][j-1] + (w[i]-w[i-1])*(w[i]-w[i-1]));
            //状态转移：两种情况取较小值  1：从序列前i-1个数中取j个代价 2：从序列前i-2个数中取j-1个的代价加上w[i]和w[的代价
        //w要是排好序的，这样所做的选择必然是相邻的两个数
        printf("%d\n",dp[n][k]);
    }
    return 0;
}