一条长为n的路,需要用路灯点亮,其中"."表示需要点亮的位置,"X"表示无需点亮的位置,假设灯立在i处,则它可以点亮i-1,i,i+1三个位置,问至少需要多少灯才能点亮整条路。
乍一看,肯定是动态规划:
上代码,敲了两个小时的动态规划:
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
using namespace std;
const int INF=10000000;
char a[105];
//到i点至少点燃了x个灯,最后一个灯的位置为j的情况下,道路被点亮了
int dp[105][105];
int main()
{
scanf("%s",a+1);
int len = strlen(a+1);
for(int i=0;i<=100;i++)
{
for(int j=0;j<=100;j++)
{
dp[i][j]=INF;
}
}
dp[0][0]=0;
for(int i=1;i<=len;i++)
{
for(int j=0;j<=i-1;j++)
{
if(dp[i-1][j]==INF) continue;
if(a[i]=='X')
{
dp[i][j]=min(dp[i][j],dp[i-1][j]);
}
else if(a[i]=='.')
{
if(j==i-1&&j!=0)
dp[i][j]=min(dp[i][j],dp[i-1][j]);
else
dp[i][i]=min(dp[i][i],dp[i-1][j]+1);
}
}
for(int j=0;j<=i-2;j++)
{
if(dp[i-2][j]==INF) continue;
if(a[i]=='X'&&a[i-1]=='X')
dp[i][j] = min(dp[i][j],dp[i-2][j]);
else
{
if(j==i-2&&j!=0)
{
if(a[i]=='X')
dp[i][j] = min(dp[i][j],dp[i-2][j]);
else if(a[i]=='.')
dp[i][i] = min(dp[i][i],dp[i-2][j]+1);
}
else
{
dp[i][i] = min(dp[i][i],dp[i-2][j]+1);
dp[i][i-1]=min(dp[i][i-1],dp[i-2][j]+1);
}
}
}
for(int j=0;j<=i-3;j++)
{
if(dp[i-3][j]==INF) continue;
if(a[i]=='X'&&a[i-1]=='X'&&a[i-2]=='X')
dp[i][j] = min(dp[i][j],dp[i-3][j]);
else
{
if(j==i-3&&j!=0)
{
if(a[i]=='X'&&a[i-1]=='X')
dp[i][j] = min(dp[i][j],dp[i-3][j]);
else
{
dp[i][i] = min(dp[i][i],dp[i-3][j]+1);
dp[i][i-1]=min(dp[i][i-1],dp[i-3][j]+1);
}
}
else
{
if(a[i]=='X')
dp[i][i-2]=min(dp[i][i-2],dp[i-3][j]+1);
else if(a[i-2]=='X')
dp[i][i]=min(dp[i][i],dp[i-3][j]+1);
else
dp[i][i-1]=min(dp[i][i-1],dp[i-3][j]+1);
}
}
}
}
for(int i=0;i<=len;i++)
{
if(dp[len][i]!=INF)
{
printf("%d\n",dp[len][i]);
break;
}
}
return 0;
}
而实际上呢,如果不要那么浮躁,再看看题目,你就会发现,这题目贪心就能解决。只要有"."在长度为3的范围内,点亮一个火把就可以了。
#include <iostream>
using namespace std;
char s[105];
int solve(char s[], int n) {
int ans = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '.') {
ans++;
s[i] = 'X';
if(i+1 < n&&s[i+1] == '.') s[i+1] = 'X';
if(i+2 < n&&s[i+2] == '.') s[i+2] = 'X';
}
}
return ans;
}
int main()
{
scanf("%s",s);
printf("%d",solve(s,strlen(s)));
return 0;
}
从这道题目,也可以看出,一个浮躁状态的人是不会多想,有一点想法就会去义无反顾的走下去,浪费时间精力,并且在没有想清楚的情况下就去否定别人的解决,想当然,并且急躁。
一个好的编程人员,一定是会有一个好的编程心境!这至关重要!