随笔 - 40, 文章 - 0, 评论 - 19, 引用 - 0
数据加载中……

2009-7-27

/*Tju 3207.   Sand Castle
http://acm.tju.edu.cn/toj/showp3207.html
排序后贪心,贪心的正确性证明很简单,只要匹配出现交叉则浪费
*/
#include
<stdio.h>
#include
<algorithm>
using namespace std;
int na[25001];
int nb[25001];

int cmp(int x , int y){
    
return x < y;
}

int main(){
    
int n , h1, h2 ;
    scanf(
"%d%d%d",&n,&h1,&h2);
    
for(int i = 0 ; i < n ; i++)
        scanf(
"%d%d",&na[i],&nb[i]);
    sort(na,na
+n,cmp);
    sort(nb,nb
+n,cmp);

    
int sum = 0;
    
for(int i = 0 ; i < n ; i++){
        
if(na[i] > nb[i]){
            sum 
+= h2 * (na[i] - nb[i]);
        }
        
else{
            sum 
+= h1 * (nb[i] - na[i]);
        }
    }
    printf(
"%d\n",sum);
    
return 0;
}
/*
TJU 3209.   Look Up
http://acm.tju.edu.cn/toj/showp3209.html
自底而上扫,纪录结果,以纪录跳转的方式优化时间
*/
#include
<stdio.h>
int a[100001];
int ans[100001];
int now;
int main(){
    
int n;
    scanf(
"%d",&n);
    
for(int i = 0 ; i <n ; i++){
        scanf(
"%d",&a[i]);
    }
    ans[n
-1= -1 ;
    
for(int i = n - 2 ; i >= 0 ; i--){
        
if(a[i]<a[i+1]){
            ans[i] 
= i + 1;
        }
        
        
else{
            now 
=  i + 1;
            
while(1){
                
if(now == -1 ){
                    
if(a[now] > a[i])
                    ans[i] 
= now;
                    
else
                    ans[i] 
= -1 ;
                    
break;
                }

                
if(a[now] > a[i] )
                {
                    ans[i] 
= now;
                    
break;
                }
                
else{
                    now 
= ans[now];
                }

            }

        }
    }
    
for(int i = 0 ; i < n ; i++)
    printf(
"%d\n",ans[i]+1);

    
return 0;
}
/*
TJU 3208.   Cow Frisbee Team
http://acm.tju.edu.cn/toj/showp3208.html
DP 控制取与不取更新更大的值 dp的两维分别代表取用前i个cow 和 余数大小
*/


#include
<stdio.h>
const int MOD=100000000;
int a[2001];
int n , f;
int dp[2001][1001];
int main(){
    scanf(
"%d%d",&n,&f);
    
for(int i = 0 ; i < n ; i++){
        scanf(
"%d",&a[i]);
    }


    dp[
0][0= 1;
    
for(int i = 0 ; i < n ; i++){
        
for(int j = 0 ; j < f ; j++){
            dp[i
+1][j] += dp[i][j] % MOD;
            dp[i
+1][(j+a[i])%f] += dp[i][j] % MOD;
        }

    }

    printf(
"%d\n",(dp[n][0]-1)%MOD);
    
return 0 ;
}

posted on 2009-07-27 02:53 hadn't 阅读(186) 评论(0)  编辑 收藏 引用


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