今日有个效益需要在网格中输入时间,本来是用文本框的,可是客户说不亮堂格式,要求用接纳的款式,好像silverlight又从未能采纳时间的控件,Google下取得一个曲线救国的答案,记录下

http://codeforces.com/contest/864/problem/E

图片 1图片 2

题意:

 1 <sdk:DataGridTemplateColumn Header="起始日期">
 2     
 3     <sdk:DataGridTemplateColumn.CellTemplate>
 4         <DataTemplate>
 5             <TextBlock Text="{Binding SellBegin}" />
 6         </DataTemplate>
 7     </sdk:DataGridTemplateColumn.CellTemplate>
 8     
 9     <sdk:DataGridTemplateColumn.CellEditingTemplate>
10         <DataTemplate>
11             <my:DatePicker SelectedDate="{Binding SellBegin}" />
12         </DataTemplate>
13     </sdk:DataGridTemplateColumn.CellEditingTemplate>
14     
15 </sdk:DataGridTemplateColumn>

有一堆物品,每个物品有3个属性,需要的岁月,失效的刻钟(一始发)和价值。只好一件一件的选料物品(即在选拔这件物品时需要自然的时刻,在这段时日之内不可以选取此外物料),拔取这件物品只好在失效时间从前采纳。问采纳的最大价值是有些。

View Code

思路:

能显得时间,可是仍旧无法采用到时间,时间部分需要手输,而且在编写状态看不到,已有找到更好的模式再改进

对于每一个物料,有选和不选两种操作,与01背包是一般的。可是此题选拔的顺序会潜移默化到结果,这是01背包不同的地方。

比如 a.st = 3,a.en = 5,a.v = 4

        b.st = 4,b.en = 8,b.v = 5

这组数据先接纳a,再选用b符合条件,价值最大,可是只要先选拔b,那么a就没得选了,所以我们需要依据一定的顺序来抉择。

这就是说通过这么些例子可以直观的感受到我们按截至时间排序之后展开分选得到的结果是最优的。

背包的时候,把日子当作体积V,然后滚动数组优化时间就得逆序枚举,时间必须是失效时间-1(因为是在失效时间按事先),然巧妙的用一个vector来保存物品的数码就足以了。

代码:

 1 #include <stdio.h>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     int s,e,v;
 9     int id;
10 
11     void read(void)
12     {
13         scanf("%d%d%d",&s,&e,&v);
14     }
15 } a[105];
16 
17 bool cmp(node aa,node bb)
18 {
19     return aa.e < bb.e;
20 }
21 
22 int dp[2005];
23 vector<int> g[2005];
24 
25 int main()
26 {
27     int n;
28 
29     scanf("%d",&n);
30 
31     for (int i = 1;i <= n;i++)
32         a[i].read(),a[i].id = i;
33 
34     sort(a+1,a+n+1,cmp);
35 
36     for (int i = 1;i <= n;i++)
37     {
38         for (int j = a[i].e - 1;j >= a[i].s;j--)
39         {
40             if (dp[j] < dp[j-a[i].s] + a[i].v)
41             {
42                 dp[j] = dp[j-a[i].s] + a[i].v;
43 
44                 g[j].clear();
45 
46                 for (int k = 0;k < g[j-a[i].s].size();k++)
47                     g[j].push_back(g[j-a[i].s][k]);
48 
49                 g[j].push_back(a[i].id);
50             }
51         }
52     }
53 
54     int ans = 0,id = 0;
55 
56     for (int i = 1;i <= a[n].e;i++)
57     {
58         if (dp[i] > ans)
59         {
60             ans = dp[i];
61             id = i;
62         }
63     }
64 
65     printf("%d\n",ans);
66     printf("%d\n",g[id].size());
67 
68     for (int i = 0;i < g[id].size();i++)
69     {
70         if (!i) printf("%d",g[id][i]);
71         else printf(" %d",g[id][i]);
72     }
73 
74     return 0;
75 }