POJ 3176 Cow Bowling

链接： http://poj.org/problem?id=3176

这道题可以算是dp入门吧。可以用一个二维数组从下向上来搜索从而得到最大值。

优化之后可以直接用一维数组来存。（PS 用一维的时候要好好想想具体应该怎么存，还是有技巧的）

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

using namespace std;

int dp[355]={0};

int main ()

{

    int n,i,j,s=0,a;

    cin>>n;

    for (i=1; i<=n; i++)

        for (j=i; j>=1; j--)

        {

            cin>>a;

            dp[j]=(dp[j]>dp[j-1]?dp[j]:dp[j-1])+a;

            //用一维数组更新的时候必须时必须保证更新后的元素在之后同一层dp中不再用到。

            if (s<dp[j]) s=dp[j];

        }

    cout<<s<<endl;

    return 0;

}

/*

int map[355][355];

int main ()

{

    int n,i,j;

    cin>>n;

    for (i=0; i<n; i++)

        for (j=0; j<=i; j++)

            cin>>map[i][j];

    for (i=n-2; i>=0; i--)

        for (j=0; j<=i; j++)

            map[i][j]+=(map[i+1][j]>map[i+1][j+1]?map[i+1][j]:map[i+1][j+1]);

            //这是开二维数组，从下向上dp

    cout<<map[0][0]<<endl;

    return 0;

}

*/

POJ 1674 Sorting by Swapping

链接： http://poj.org/problem?id=1674

题意是有一串数字，问你最少交换多少次可以得到从小到大的排序

我们知道最少交换次数可以用选择排序来求得。但是这道题如果用选择排序的话，必然超时。

其实这道题还是暗藏玄机的。因为n个数正好是1到n。所以如果a[i]==i 就表示该位置已经排好了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#define p 3.1415927

using namespace std;

int a[10010]= {0};

int main ()

{

    int t,n,i,j;

    cin>>t;

    while(t--)

    {

        int s=0;

        cin>>n;

        for (i=0; i<n; i++)

            scanf("%d",a+i);

        for (i=0; i<n-1; i++)

            if (a[i]!=i+1)//这道题如果用选择排序的话。10000^2。必然超时

            //这道题n个数是从1到n。所以加这个判断会适当减时

            {

                for (j=i+1; j<n; j++)

                    if (a[j]==i+1)

                    {

                        int temp=a[j];

                        a[j]=a[i];

                        a[i]=temp;

                        s++;

                    }

            }

        cout<<s<<endl;

    }

    return 0;

}

POJ 2346 Lucky Tickets

链接： http://poj.org/problem?id=2346

这道题就是一个n位数，左半边相加和有半边相加相等为一个组合，问有多少组合。n位数可以有前导零

由于n最大为10.。想都没想直接打表了。。

不过看discuss里面说这道题可以dp。好神。不过想想也是

这道题还应该再思考思考

//这道题有待提高 用DP来做 以后试试

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int main ()

{

    int a[6]={0,10,670,55252,4816030,432457640};

    int n;

    cin>>n;

    cout<<a[n/2]<<endl;

}

这几天做了挺多水题的。为了增快阅读速度吧。还有就是要加快敲代码速度。

这里面几道题目都是相对有点意思的。