UOJ Logo chtomede的博客

博客

#143. 最佳旅游线路

2019-02-03 00:25:29 By chtomede

贪心+一点点DP

直接上代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,a[1000][100000],dp[10000];
int main(){
    memset(dp,-111,sizeof(dp));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<m;i++)
        for(int j=1;j<=n;j++)
            dp[i]=max(dp[i],a[j][i]);
    for(int i=1;i<m;i++){
        dp[i]=max(dp[i],dp[i]+dp[i-1]);
        dp[0]=max(dp[i],dp[0]);
    }
    cout<<dp[0]<<endl;
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。