当前位置:编程学习 > C/C++ >>

UVALive 6208

离散DP

由于状态转移需要记录三维,第三维是之前的高度,而这个变量取值只有离散的几个,故用map来存。

不过一开始一直T啊,最后加些剪枝终于过了。。。


[cpp]
#include <iostream>  
#include <cstdio>  
#include <string>  
#include <cstring>  
#include <algorithm>  
#include <map>  
using namespace std; 
const int inf =((~(0U))>>1); 
struct Point{ 
    int x,y; 
}point[100]; 
 
bool cmp(struct Point a,struct Point b){ 
    return a.y*b.x > a.x*b.y; 

 
map<int,int> dp[60][60]; 
 
int main(){ 
    int t,T,n,kk,i,j,k; 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d %d",&n,&kk); 
        for(i=1;i<=n;i++) scanf("%d %d",&point[i].x,&point[i].y); 
        sort(point+1,point+n+1,cmp); 
        for(i=1;i<=n;i++) 
            for(j=1;j<=kk;j++) dp[i][j].clear(); 
        for(i=0;i<=n;i++) 
            dp[i][0][0]=0; 
        //for(i=1;i<=n;i++) printf("***%d %d\n",point[i].x,point[i].y);  
        int t1,t2; 
        for(i=1;i<=n;i++){ 
            for(j=1;j<=i && j<=kk;j++){ 
                if(j+n-i<kk)continue; 
                t1=0;t2=0; 
                dp[i][j]=dp[i-1][j]; 
                for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){ 
                    if(k->first+point[i].y<t1 && k->second+(k->first*2+point[i].y)*point[i].x<t2) continue; 
                    t1=k->first+point[i].y; 
                    t2=k->second+(k->first*2+point[i].y)*point[i].x; 
                } 
                for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){ 
                    if(k->first+point[i].y<t1 && k->second+(k->first*2+point[i].y)*point[i].x<t2) continue; 
                    dp[i][j][k->first+point[i].y]=max(dp[i][j][k->first+point[i].y],k->second+(k->first*2+point[i].y)*point[i].x); 
                } 
            } 
        } 
        int ans=0; 
        for(i=1;i<=n;i++){ 
            for(map<int,int>::iterator k=dp[i][kk].begin();k!=dp[i][kk].end();k++){ 
                ans=max(ans,k->second); 
            } 
        } 
        printf("Case %d: %d\n",t,ans); 
    } 
    return 0; 

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int inf =((~(0U))>>1);
struct Point{
    int x,y;
}point[100];

bool cmp(struct Point a,struct Point b){
    return a.y*b.x > a.x*b.y;
}

map<int,int> dp[60][60];

int main(){
    int t,T,n,kk,i,j,k;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d %d",&n,&kk);
        for(i=1;i<=n;i++) scanf("%d %d",&point[i].x,&point[i].y);
        sort(point+1,point+n+1,cmp);
        for(i=1;i<=n;i++)
            for(j=1;j<=kk;j++) dp[i][j].clear();
        for(i=0;i<=n;i++)
            dp[i][0][0]=0;
        //for(i=1;i<=n;i++) printf("***%d %d\n",point[i].x,point[i].y);
        int t1,t2;
        for(i=1;i<=n;i++){
            for(j=1;j<=i && j<=kk;j++){
                if(j+n-i<kk)continue;
                t1=0;t2=0;
                dp[i][j]=dp[i-1][j];
                for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){
                    if(k->first+point[i].y<t1 && k->second+(k->first*2+point[i].y)*point[i].x<t2) continue;
                    t1=k->first+point[i].y;
                    t2=k->second+(k->first*2+point[i].y)*point[i].x;
                }
                for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,