比这篇新的文章: 一个用wxPython实现有FLASH播放器（转贴）
比这篇旧的文章: shulie.cpp

P1150.cpp

语言: C++, 标签: 无  2008/08/22发布 3个月前更新
作者: xpycc, 点击401次, 评论(3), 收藏者(0)

开关行号, 全选(Ctrl+C复制) | 一键复制:HTML, BBCode(Discuz!) , 源代码 | 查看:裸代码, 全屏
背景
主题: 字体:
C++语言: P1150.cpp
01 #include <iostream>
02 using namespace std;
03
04 long f[2][100][100],c[100][100];
05 int w[100],d[100];
06
07 int main(){
08     int n,v,i,j;
09     long s=0;
10     cin>>n>>v;
11     for(i=1;i<=n;++i){
12         cin>>d[i]>>w[i];
13         s+=w[i];
14     }
15     for(i=1;i<=n;++i){
16         c[i][i]=s-w[i];
17         for(j=i+1;j<=n;++j)
18         c[i][j]=c[i][j-1]-w[j];
19     }
20
21     for(i=1;i<v;++i){
22         f[0][i][0]=f[0][i-1][0]+c[v-i+1][v]*(d[v-i+1]-d[v-i]);
23         f[1][i][0]=f[0][i][0]+c[v-i][v]*(d[v]-d[v-i]);
24     }
25     for(j=1;j<=n-v;++j){
26         f[1][0][j]=f[1][0][j-1]+c[v][v+j-1]*(d[v+j]-d[v+j-1]);
27         f[0][0][j]=f[1][0][j]+c[v][v+j]*(d[v+j]-d[v]);
28     }
29
30     for(i=1;i<v;++i)
31         for(j=1;j<=n-v;++j){
32             if(f[0][i-1][j]+(d[v-i+1]-d[v-i])*c[v-i+1][v+j]<
33                f[1][i-1][j]+(d[v+j]-d[v-i])*c[v-i+1][v+j])
34                 f[0][i][j]=f[0][i-1][j]+(d[v-i+1]-d[v-i])*c[v-i+1][v+j];
35             else f[0][i][j]=f[1][i-1][j]+(d[v+j]-d[v-i])*c[v-i+1][v+j];
36
37             if(f[1][i][j-1]+(d[v+j]-d[v+j-1])*c[v-i][v+j-1]<
38                f[0][i][j-1]+(d[v+j]-d[v-i])*c[v-i][v+j-1])
39                 f[1][i][j]=f[1][i][j-1]+(d[v+j]-d[v+j-1])*c[v-i][v+j-1];
40             else f[1][i][j]=f[0][i][j-1]+(d[v+j]-d[v-i])*c[v-i][v+j-1];
41         }
42
43     f[0][v-1][n-v]<f[1][v-1][n-v]?cout<<f[0][v-1][n-v]:cout<<f[1][v-1][n-v];
44     cout<<endl;
45
46     return 0;
47 }
打分:

所有评论，共3条：( 我也来说两句)

1
半瓶墨水 2个月前 回复
踢 0
0 赞
天，搞搞注释啊，谁知道这是虾米东西？
2
innersmile 2个月前 回复
踢 0
0 赞
haha, 不过在这位兄弟的帮忙下，发芽网代码篇数终于超过用户数了！
3
半瓶墨水 2个月前 回复
踢 0
0 赞
@2: 汗  这倒是没错儿。。。

发表评论

请注册并登录后再发表评论