int超内存 要用short或者滚动数组
滚动数组
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; char s1[5050],s2[5050]; int dp[2][5050],n; int main() { int i,j; while(~scanf("%d",&n)) { scanf("%s",s1); for(i=n-1,j=0;i>=0;i--,j++) s2[i]=s1[j]; memset(dp,0,sizeof dp); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dp[i%2][j]=dp[(i-1)%2][j]>dp[i%2][j-1] dp[(i-1)%2][j]:dp[i%2][j-1]; if(s1[i-1]==s2[j-1]) dp[i%2][j]=dp[(i-1)%2][j-1]+1>dp[i%2][j] dp[(i-1)%2][j-1]+1:dp[i%2][j]; } } printf("%d\n",n-dp[n%2][n]); } return 0; }
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; char s1[5050],s2[5050]; short dp[5050][5050],n; int main() { int i,j; while(~scanf("%d",&n)) { scanf("%s",s1); for(i=n-1,j=0;i>=0;i--,j++) s2[i]=s1[j]; memset(dp,0,sizeof dp); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dp[i][j]=dp[i-1][j]>dp[i][j-1] dp[i-1][j]:dp[i][j-1]; if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1>dp[i][j] dp[i-1][j-1]+1:dp[i][j]; } } printf("%d\n",n-dp[n][n]); } return 0; }