Fireworks焦祺_第二周
星期六:
虽然历经波折,但是这道题还是解得比较成功的一道题
有一种很很强烈的感觉,这到是简单题,于是不断地想各种方法解出来
一拿到题我就用直接模拟的方法,但是很容易就出错了
发现如果要完整一点的话就得用DFS了,但是很容易TLE了
后来我想了很多种方法去优化我的DFS----未果
最后一次我HASH都用上了,但是TLE得很惨烈.(下续)
HDOJ 2546饭卡 http://acm.hdu.edu.cn/showproblem.php?pid=2546
Problem Description
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
Sample Output
-45
32
(续上)
这都不行的话那只有DP了,我的DP很弱,但是后来的一次专题训练让我开了点窍
于是我翻出以前的DP总结出来看,便有了灵感:
这得利于我之前就把题目的化解为求一组的子序列和<=m-5的数里的最大数
听起来很费劲,但是如果要表达得更好恐怕不是一句话可以解决的
求解模型: 求序列的最大上升序列
经典的例题可以访问:
http://blog.csdn.net/jqandjq/archive/2009/02/26/3940712.aspx
具体方法:
建另一个数组.来记录每一遍历到的数的最优情况.
下面是我的代码,于由是从DFS的代码改过来的,所以有一些冗余的部分.
#include <iostream>
#include <algorithm>
using namespace std;
int a[1002];
int b[1002];
void dfs(int x);
int m;
int sum,num,ans,flag;
int main()
{
int i,j,k,n,t;
while(scanf("%d",&n)!=EOF && n)
{
memset(b,0,sizeof(b));
sum = 0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum += a[i];
}
scanf("%d",&m);
if (sum+5 <= m) //如果余额很大的情况
{
printf("%d/n",m-sum);
continue;
}
if (m < 5) //如果本来的余额小于5那么就不用计算了
{
printf("%d/n",m);
continue;
}
sort(a,a+n);
//开始遍历:
//找到临界大于m-5的最小的和
ans = 0;
num = m - 5;
for(i=n-2;i>=0;i--)
{
int maxnum = 0;
for(j=i+1;j<=n-2;j++)
{
if((b[j] > maxnum) && (a[i]+b[j]<=num) )
maxnum = b[j];
}
if(a[i]+maxnum == num)
{
ans = num;
break;
}
else if(a[i]+maxnum < num)
{
b[i] = a[i]+maxnum;
}
if(b[i] > ans)
ans = b[i];
}
printf("%d/n",m-ans-a[n-1]);
}
return 0;
}
星期日:
上星期遗下的题目还有一道没有完成
PKU 2262 Goldbach's Conjecture
http://acm.pku.edu.cn/JudgeOnline/problem?id=2262
主要是用高效点的求素数的方法
#include <iostream>
using namespace std;
const int N = 1000005;
bool a[N];
int p[N];
// bool hash[1000005]; 记录某数是否为素数
void Prime2(int n) //线性法,参数表示要打多少内的素数
{
memset(a, 0, n*sizeof(a[0]));
// memset(hash,0,sizeof(hash));
int num = 0, i, j;
for(i = 2; i < n; ++i)
{
if(!(a[i]))
{
p[num++] = i;
// hash[i] = 1;
}
for(j = 0; (j<num && i*p[j]<n); ++j)
{
a[i*p[j]] = 1;
if(!(i%p[j])) break;
}
}
}
int main()
{
int i,j,k,n,m,t;
Prime2(1000001);
while (scanf("%d",&n)!=EOF && n)
{
for (i=0;p[i]<=n/2;i++)
{
if (hash[n - p[i]])
{
printf("%d = %d + %d/n",n,p[i],n-p[i]);
break;
}
}
}
return 0;
}
星期一:
没办法,要检查题数了,只好狂A简单题咯~~~
HDOJ 1062 Text Reverse http://acm.hdu.edu.cn/showproblem.php?pid=1062
简单的字符串控制,之前好像做过,不过题库里这里还没打勾…..
之前还很菜的时候在训练时还A错了几次..而且没A出来
今天十几分钟自信地A掉.
CODE: (水题不直接贴了)
http://blog.csdn.net/jqandjq/archive/2009/03/23/4018038.aspx
HDOJ 1088 Write a simple HTML Browser
http://acm.hdu.edu.cn/showproblem.php?pid=1088
字符串的控制,理解好题意.
不过这题还是有点变态的.
#include <iostream>
using namespace std;
char str[200];
#define hr "--------------------------------------------------------------------------------"
int main()
{
int i,j,k,n,m,t;
int sum = 0;
// freopen("12.txt","r",stdin);
// freopen("123.txt","w",stdout);
while (scanf("%s",str)!=EOF)
{
if (strcmp(str,"<br>") == 0)
{
sum = 0;
printf("/n");
}
else if (strcmp(str,"<hr>") == 0)
{
if (sum == 0)
{
printf("%s/n",hr);
}
else
{
sum = 0;
printf("/n%s/n",hr);
}
}
else
{
if (sum==0)
{
printf("%s",str);
sum += strlen(str);
}
else
{
if (sum + strlen(str) + 1<=80)
{
printf(" %s",str);
sum += strlen(str) + 1;
}
else
{