【POJ】Cow Bowling

Problem here

Description

The cows don’t use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:

      7



    3   8



  8   1   0



2   7   4   4

4 5 2 6 5 
Then the other cows traverse the triangle starting from its tip and moving “down” to one of the two diagonally adjacent cows until the “bottom” row is reached. The cow’s score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame.

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output

Line 1: The largest sum achievable using the traversal rules

Sample Input

5 
7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5

Sample Output

30

Hint

Explanation of the sample:

      7

     *

    3   8

   *

  8   1   0

   *

2   7   4   4

   *

4 5 2 6 5 
The highest score is achievable by traversing the cows as shown above.

Solution

#include <iostream>
#include <memory.h>
using namespace std;

int dp[355][355], cost[355][355];

int main(){

    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cin >> cost[i][j];
        }
    }
    dp[0][0] = cost[0][0];
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j - 1 < 0)
                dp[i][j] = dp[i-1][j] + cost[i][j];
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + cost[i][j];
        }
    }
    int answer = 0;
    for(int i = 0; i < n; i++){
        if(answer < dp[n-1][i])
            answer = dp[n-1][i];
    }
    cout << answer << endl;
    return 0;
}

【UVa】10298 - Power Strings

Problem here

---

Given two strings a and b we define a ∗ b to be their concatenation. For 
example, if a = ‘abc’ and b = ‘def’ then a ∗ b = ‘abcdef’. If we think of 
concatenation as multiplication, exponentiation by a non-negative integer 
is defined in the normal way: a 
0 = ‘’ (the empty string) and a 
(n+1) = 
a ∗ (a 
n).

Input

Each test case is a line of input representing s, a string of printable characters. 
The length of s will be at least 1 and will not exceed 1 million 
characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a 
n for some string 
a.

Sample Input

abcd 
aaaa 
ababab 
.

Sample Output

1 
4 
3

Solution

#include <iostream>
#include <string>
//#include <fstream>
#define MAX_NUM 9999999
using namespace std;

//ifstream fin("10298.in");
//ofstream fout("10298.out");

int next_pos[1000001];

void getNext(string str){
    next_pos[0] = -1;
    int j = 0, k = -1;
    while(j < str.size()){
        if(k == -1 || str[j] == str[k]){
            next_pos[++j] = ++k;
        }
        else{
            k = next_pos[k];
        }
    }
}

int main(){
    string input;
    while(cin >> input){
        if(input == ".")
            break;

        getNext(input);
        int length = input.size();
        if(length % (length- next_pos[length]) == 0 && next_pos[length] != 0)
            cout << length / (length - next_pos[length]) << endl;
        else
            cout << 1 << endl;
    }

    return 0;
}

【UVa】455 - Periodic Strings

Problem here 
A character string is said to have period k if it can be formed by concatenating one or more repetitions 
of another string of length k. For example, the string ”abcabcabcabc” has period 3, since it is formed 
by 4 repetitions of the string ”abc”. It also has periods 6 (two repetitions of ”abcabc”) and 12 (one 
repetition of ”abcabcabcabc”). 
Write a program to read a character string and determine its smallest period.

Input

The first line oif the input file will contain a single integer N indicating how many test case that your 
program will test followed by a blank line. Each test case will contain a single character string of up 
to 80 non-blank characters. Two consecutive input will separated by a blank line.

Output

An integer denoting the smallest period of the input string for each input. Two consecutive output are 
separated by a blank line.

Sample Input

1 
HoHoHo

Sample Output

2

Solution

#include <iostream>
#include <string>
using namespace std;

int main(){
    int kase;
    cin >> kase;

    while(kase--){
        string line;
        getline(cin, line);
        bool pass = false;
        string input;
        cin >> input;
        for(int i = 1; i <= input.size()-1; i++){
            if(input.size() % i == 0){
                int j;
                for(j = i; j < input.size(); j++){
                    if(input[j] != input[j%i])
                        break;
                }
                if(j == input.size()){
                    cout << i << endl;
                    pass = true;
                    break;
                }
            }
        }
        if(!pass)
            cout << input.size() << endl;
        if(kase)
            cout << endl;
    }
    return 0;
}

【TopCoder】ZigZag - 2003 TCCC Semifinals 3

Problem Statement

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. 
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. 
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Solution

class ZigZag{
    public:
        int longestZigZag(vector<int> numbers){
            vector<int> dp(numbers.size(), 1);
            vector<int> mark(numbers.size(), 0);
            for(int i = 1; i < numbers.size(); i++){
                for(int j = 0; j < i; j++){
                    int tmp = numbers[i] - numbers[j];
                    if(tmp > 0 && mark[j] <= 0 && dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        mark[i] = 1;
                    }else if(tmp < 0 && mark[j] >= 0 && dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        mark[i] = -1;
                    }
                }
            }
            sort(dp.begin(), dp.end());

            return dp[numbers.size()-1];
        }
};