O(1) 的小乐

Job Hunting

公告

记录我的生活和工作。。。
<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

统计

  • 随笔 - 182
  • 文章 - 1
  • 评论 - 41
  • 引用 - 0

留言簿(10)

随笔分类(70)

随笔档案(182)

文章档案(1)

如影随形

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜

USACO 2.3 Money Systems

/*
ID: lvxiaol3
LANG: C++
TASK: money
*/
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <cstdio>
using namespace std;

 

int main()
{
    ifstream fin("money.in");
    ofstream fout("money.out");
    int V, N;
    fin>>V>>N;
    vector<int> Coin(V);
    for(int i=0; i<V; i++) fin>>Coin[i];
    sort(Coin.begin(),Coin.end());

    long long  dp[2][10005];
    for(int i=0;i<V; i++) dp[i%2][0]=1LL;
    int temp=Coin[0];
    while(temp<=N) {dp[0][temp]=1;temp+=Coin[0];}

    for(int i=1; i<V;i++)
    {
        for(int j=1;j<=N;j++)
        {
            int m=j;
            dp[i%2][j]=0;
            while(m>=0)
            {
                dp[i%2][j]+=dp[(i-1)%2][m];
                m-=Coin[i];
            }
        }
    }
    fout<<dp[(V-1)%2][N]<<endl;


    return 0;
}
/*
3 10
1 2 5

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

Process returned 0 (0x0)   execution time : 0.027 s
Press any key to continue.

*/
// dp[k][n] the previous k kind of coins consist of n
// dp[k][n]= /sum{dp[k-1][n-p*v[k]] } p>=0

 

下面这一步的dp优化赞!利用DP状态改变的顺序来优化dp的复杂度
/*
for(i=0; i<v; i++) {
        fscanf(fin, "%d", &c);

        for(j=c; j<=n; j++)
            nway[j] += nway[j-c];
    }
*/

posted on 2011-10-19 22:14 Sosi 阅读(114) 评论(0)  编辑 收藏 引用


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


统计系统