水 A - Kefa and First Steps

/************************************************

* Author        :Running_Time

* Created Time  :2015/9/23 星期三 00:19:33

* File Name     :A.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-8;

int a[N];

int main(void)    {

	int n;	scanf ("%d", &n);

	for (int i=1; i<=n; ++i)	{

		scanf ("%d", &a[i]);

	}

	int l = 1;

	int ans = 1;	int pre = a[1];

	for (int i=2; i<=n; ++i)	{

		if (a[i] >= pre)	{

			pre = a[i];	ans = max (ans, i - l + 1);

		}

		else	{

			pre = a[i];	l = i;

		}

	}

	printf ("%d\n", ans);

    return 0;

}

　　

尺取法 B - Kefa and Company

题意：每个朋友有他的金钱和友好程度，从朋友中选取一些人，问在贫富差距小于d的最大友好程度和为多少

分析：先按照m金钱从小到大排序，枚举每个起点看以这个人为最穷的人能得到的最大友好程度多少，然后是第二穷的人。。。。。复杂度O (nlogn)，尺取法也叫two points ？

/************************************************

* Author        :Running_Time

* Created Time  :2015/9/23 星期三 00:19:38

* File Name     :B.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-8;

struct Friend	{

	int m, s;

	bool operator < (const Friend &r) const {

		return m < r.m;

	}

}f[N];

int main(void)    {

	int n, d, mn = INF, mx = -1;

	ll sum = 0;

	scanf ("%d%d", &n, &d);

	for (int i=1; i<=n; ++i)	{

		scanf ("%d%d", &f[i].m, &f[i].s);

		if (f[i].m > mx)	mx = f[i].m;

		if (f[i].m < mn)	mn = f[i].m;

		sum += f[i].s;

	}

	if (mx - mn < d)	{

		printf ("%I64d\n", sum);	return 0;

	}

	sort (f+1, f+1+n);

	int l = 1, r = 2;

	ll ans = f[1].s;	sum = f[1].s;

	while (true)	{

		while (r <= n && f[r].m - f[l].m < d)	{

			sum += f[r++].s;

		}

		ans = max (ans, sum);

		if (r > n)	break;

		sum -= f[l++].s;

	}

	printf ("%I64d\n", ans);

    return 0;

}

　　

DFS C - Kefa and Park

题意：从根节点1出发，到底部的点的路径没有超过连续m个点有cat的个数为多少

分析：简单的深搜，记录走到当前点最大连续cat数，注意一些剪枝

/************************************************

* Author        :Running_Time

* Created Time  :2015/9/23 星期三 00:19:41

* File Name     :C.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-8;

vector<int> G[N];

int cat[N];

bool vis[N];

int n, m, ans;

void DFS(int u, int fa, int num)	{

	for (int i=0; i<G[u].size (); ++i)	{

		int v = G[u][i];

		if (vis[v] || v == fa)	continue;

		if (cat[v])	{

			if (num + 1 <= m)	{				//算上当前点，cat + 1

				if (G[v].size () == 1)	{		//到达底部

					vis[v] = true;	ans++;

				}

				else	{

					vis[v] = true;				//未到达底部

					DFS (v, u, num + 1);

				}

			}

			else	continue;					//条件不符，不往下艘

		}

		else	{

			if (num <= m)	{

				if (G[v].size () == 1)	{

					vis[v] = true;	ans++;

				}

				else	{

					vis[v] = true;

					DFS (v, u, 0);

				}

			}

			else	continue;

		}

	}

}

int main(void)    {

	scanf ("%d%d", &n, &m);

	for (int i=1; i<=n; ++i)	{

		scanf ("%d", &cat[i]);

	}

	for (int u, v, i=1; i<n; ++i)	{

		scanf ("%d%d", &u, &v);

		G[u].push_back (v);

		G[v].push_back (u);

	}

	DFS (1, 0, cat[1]);

	printf ("%d\n", ans);

    return 0;

}

　　

状态压缩DP D - Kefa and Dishes

题意：n道菜选择m道，每道菜有一个愉悦度，如果某些菜按照先后顺序吃还能得到额外的愉悦度，问最大愉悦度为多少

分析：其实就是一个DAG问题，数据范围18应该想到状压，我不熟悉以为数据范围太大，做不了。dp[mask][i] 表示当在mask集合状态下，最后是第i道菜的最大愉悦度为多少，状态转移方程：dp[(i|(1<<l))][l] = max (dp[i][j] + a[l] + g[j][l])  复杂度O(2n * n2).

/************************************************

* Author        :Running_Time

* Created Time  :2015/9/23 星期三 01:49:58

* File Name     :D.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 18;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-8;

int n, m, k;

ll dp[(1<<N)+10][N];

int a[N];

int g[N][N];

int main(void)    {

	scanf ("%d%d%d", &n, &m, &k);

	for (int i=0; i<n; ++i)	{

		scanf ("%d", &a[i]);

	}

	for (int u, v, c, i=1; i<=k; ++i)	{

		scanf ("%d%d%d", &u, &v, &c);

		if (g[u-1][v-1] < c)	g[u-1][v-1] = c;

	}

	int maxS = (1 << n);

	for (int i=0; i<n; ++i)	{

		dp[(1<<i)][i] = a[i];

	}

	for (int i=1; i<maxS; ++i)	{

		for (int j=0; j<n; ++j)	{

			if ((i & (1 << j)) == 0)	continue;

			for (int l=0; l<n; ++l)	{

				if ((i & (1 << l)) == 0)	{

					if (dp[(i|(1<<l))][l] < dp[i][j] + a[l] + g[j][l])	{

						dp[(i|(1<<l))][l] = dp[i][j] + a[l] + g[j][l];

					}

				}

			}

		}

	}

	ll ans = 0;

	for (int i=1; i<maxS; ++i)	{

		int cnt = 0;

		for (int j=0; j<n; ++j)	{

			if ((i & (1 << j)) != 0)	cnt++;

		}

		if (cnt == m)	{

			for (int j=0; j<n; ++j)	{

				if ((i & (1 << j)) != 0)	{

					if (ans < dp[i][j])	ans = dp[i][j];

				}

			}

		}

	}

	printf ("%I64d\n", ans);

    return 0;

}

　　

最新文章

  1. Day23_IO第五天
  2. QGC 支付宝无法异步通知及异步通知常见问题注意事项
  3. MMORGP大型游戏设计与开发（客户端架构 part13 of vegine）
  4. RouterOS软路由设置固定IP+PPPOE
  5. java 项目打包流程速记
  6. Struts2的处理结果（二）——处理结果的类型
  7. 浅谈IT
  8. ***PHP 去除换行符
  9. easyui源码翻译1.32--Calendar(日历)
  10. NGUI-学习笔记（2）一个项目需求
  11. Object.defineProperty 规则
  12. postgres中的merge join
  13. shell字符串长度
  14. mongoDB查询及游标
  15. 解决Highcharts 5.0.7，IE8下bar类型图表无法显示的问题
  16. sChart.js：一个小型简单的图表库
  17. [Python Study Notes] 变量/编码/注释
  18. Git常用命令总结（超实用）【转】
  19. 【Java线程安全】锁
  20. ldap集成x-pack

热门文章

  1. GuozhongCrawler系列教程 （5） TransactionRequest具体解释
  2. 【bzoj3210】花神的浇花集会
  3. A nonrecursive list compacting algorithm
  4. firefox 45 版本
  5. GUI界面资源
  6. POJ1759 Garland —— 二分
  7. linux初级学习笔记八：linux权限管理及权限管理命令详解！(视频序号：04_2)
  8. springboot web项目搭建
  9. MyBatis学习 之 三、SQL语句映射文件(2)增删改查、参数、缓存
  10. 「LuoguP3191」 [HNOI2007]紧急疏散EVACUATE（最大流