上善若水

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  2 Posts :: 32 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

最新随笔

搜索

  •  

积分与排名

  • 积分 - 10174
  • 排名 - 1166

最新评论

阅读排行榜

评论排行榜

Cow Solitaire

时间限制(普通/Java):1000MS/10000MS          运行内存限制:65536KByte
总提交:507            测试通过:294

描述

Late summer on the farm is a slow time, very slow. Betsy has little to do but play cow solitaire. For self-evident reasons, cow solitaire is not so challenging as any number of solitaire games played by humans.

Cow solitaire is played using an N x N (3 <= N <= 7) grid of ordinary playing cards with four suits (Clubs, Diamonds, Hearts, and Spaces) of 13 cards (Ace, 2, 3, 4, ..., 10, Jack, Queen, King). Cards are named with two characters: their value (A, 2, 3, 4, ..., 9, T, J, Q, K) followed by their suit (C, D, H, S). Below is a typical grid when N = 4:

     8S AD 3C AC     (Eight of Spades, Ace of Diamonds, etc.)
     8C 4H QD QS
     5D 9H KC 7H
     TC QC AS 2D

To play this solitaire game, Betsy starts in the lower left corner (TC) and proceeds using exactly 2*N-2 moves of 'right' or 'up' to the upper right corner. Along the way, she accumulates points for each card (Ace is worth 1 point, 2 is worth 2 points, ..., 9 is worth 9 points, T is worth 10 points, J is 11, Q is 12, and K is 13) she traverses. Her goal is to amass the highest score.

If Betsy's path was TC-QC-AS-2C-7H-QS-AC, her score would be 10+12+1+2+7+12+1=45. Had she taken the left side then top (TC-5D-8C-8S-AD-3C-AC), her score would be 10+5+8+8+1+3+1=36, not as good as the other route. The best score for this grid is 69 points (TC-QC-9H-KC-QD-QS-AC => 10+12+9+13+12+12+1).Betsy wants to know the best score she can achieve. One of the geek cows once told her something about "working from the end back to the beginning," but she didn't understand what they meant.

输入

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 lists the cards on row i (row 1 is the top row) using N space-separated card names arranged in the obvious order.

输出

* Line 1: A single line with an integer that is the best possible score Betsy can achieve.

样例输入

4
8S AD 3C AC
8C 4H QD QS
5D 9H KC 7H
TC QC AS 2D

样例输出

69

题目来源

Elite 2007 US Open Competition

分析:首先应该是转换模型,然后开始想到组合数,后来想到太繁琐,随后想到dp,从右上到左下依次+上面和右面较大的数。直到左下结束。不知道还有没有更好的办法。时间复杂度(n2)。
代码如下:
#include <stdio.h>
#include 
<stdlib.h>
#include 
<string>
int main()
{
    
int n,i,j,k;
    
char ch1,ch2,ch3;
    scanf(
"%d",&n);
    getchar();
    
int p[10][10]={0};
    memset(p,
0,sizeof(p));
    
for (i=1;i<=n;i++)
    
{
        
for (j=0;j<n;j++)
        
{
            scanf(
"%c%c%c",&ch1,&ch2,&ch2);
            
switch(ch1)
            
{
            
case 'A':k=1;break;
            
case 'T':k=10;break;
            
case 'J':k=11;break;
            
case 'Q':k=12;break;
            
case 'K':k=13;break;
            
default:k=ch1-48;
            }

            p[i][j]
=k;
        }

    }

    
//
    for (i=1;i<=n;i++)
    
{
        
for (j=n-1;j>=0;j--)
        
{
            p[i][j]
+=(p[i-1][j]>p[i][j+1]?p[i-1][j]:p[i][j+1]);
        }

    }

    printf(
"%d\n",p[n][0]);
}
posted on 2009-11-24 11:11 上善若水 阅读(122) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理